Depth first or breadth first ordering in binary search trees? Let's say that I make a binary search tree and store it in an array so that I end up with an array that is more cache friendly to binary search compared to a sorted array.

The binary tree is full on all levels except possibly the last level, where it is filled from left to right.

Specifically index 0 is the root node, and to get to a left child, you multiply current index by 2 and add 1.  To get to a right child you multiply current index by 2 and add 2.

Going this route, as i understand it, the node order is breadth first.

I've seen people mention that depth first is better (in a paper about parallel GPU bvh construction), and was wondering, is there a good reason to choose depth first over breadth first, or is it highly dependent on specific usage patterns?

Think about what happens when you move from one layer in the tree to the next. When you start getting to layers with progressively more nodes, you'll eventually get to a spot where the layers are so big that they can't fit into memory caches. When that happens, if you've laid out the memory in a BFS order, then going from one layer to the next will almost always cause a cache miss because the memory fetched for the first layer won't include the node from the next layer in it. In other words, every link followed will cause a cache miss. On the other hand, if you use DFS order, then the memory for the nodes will have the nodes broken apart into smaller chains of nodes corresponding to the paths taken by DFS. If you do lookups in a way that follows those chains, it's possible that you'll have no cache misses at all when going from one node to the next, which can dramatically speed up lookups.

The ordering I've actually heard most for making cache-friendly BSTs is the van Emde Boas layout, which is formed as follows:

If the tree has height two or less, lay it out in DFS or BFS order (they're the same here).
Otherwise, split the tree at the middle level into a "top tree" of the first half of the nodes and up to $\sqrt{n}$ "bottom trees" formed from the lower levels. Recursively compute the van Emde Boas layouts of each of these trees, then concatenate them together in order.

You can prove that this layout is optimal assuming that you don't know anything about the particular sizes of the caches of the machines in the computer (it's known as a cache-oblivious data structure).

If you do know the cache size, though, the "best" choice is probably to use a B-tree instead of a BST, since B-trees are specifically designed to play nicely with caches. Although they were designed for on-disk storage, they work really well in main memory, as some recent work has shown.


Proving that $ \{u\#v\#w \mid u,v,w \in {a,b,c}*, |u|_a = |v|_b = |w|_c\}$ isn't context-free I have a question about the pumping lemma for context-free languages.
I understand the conditions of the pumping lemma.
Assume $L$ is context-free. Let $n>0$ be the pumping length given by the lemma.
$z=uvwxy$ with conditions:

$|vwx|\leq n$

$|vx|\geq 1$

$\forall i >0,  \exists  z= uv^iwx^iy \in L$

But i need to know what are the possible cases for the $vx$, alternatively $vwx$,  so when pumped we can argue it does not  belong to the language, and if the # symbol affects the assumption?
$$L = \{u\#v\#w \mid u,v,w \in \{a,b,c\}^* , |u|_a = |v|_b = |w|_c\}$$
From what I understand, I can assume that $v$ or $y$ are only in first part $u$ or second $v$ or $w$,
but also $vxy$ can be in between $a$'s and $b$'s, including the $\#$ between them.

Condition 3 as in the question, "$\forall i >0,  \exists  z= uv^iwx^iy \in L$" does not make sense. It should be "$uv^iwx^iy \in L\text{ for all } i\ge0$", i.e., $uv^0wx^0y=uwy$, $uv^1wx^1y=uvwxy$, $uv^2wx^2y$, $uv^3wx^3y$, $uv^4wx^4y$, and so on are in $L$. Please note the first word, $uwy$, where $v$ and $x$ do not appear, i.e, we "pump down" $uvwxy$ to $uwy$.
The difficulty of applying pumping lemma comes from, indeed, recognizing "the possible cases for the $vx$" correctly and organizing them in a way that is easy to pump the word up or down to be not in the language.
Since the condition on the words in $L$ is about the number of $a$s, $b$s or $c$s in them, we will classify $v$ and $x$ also in the number of $a$s, $b$s or $c$s in them. For pumping length ${n}$, we will let $z$ be $a^n\#b^n\#c^n$, the simplest word in $L$ with length at least $n$.

If either $v$ or $x$ contains $\#$, $uwy$ will have less than 2 $\#$s, hence not a word in $L$.

Otherwise, all symbols in $v$ must be the same, and all symbols in $x$ must be the same.
Since we have 3 symbols, $a,b,c$ in $z$, (at least) one of $a,b,c$ will be missing in $vx$.
The number of $a$s, the number of $b$s and the number $c$s in $uvwxy$ are the same. Since $uv^2wx^2y$ is $vx$ "more than" $uvwxy$, the number of that missing symbol in $uv^2wx^2y$,  will be less than both the number of $s_v$ in it if $s_v$ is the symbol in $v$, and the number of $s_x$ in it if $s_x$ is the symbol in $x$.
Since $|vx|\ge1$, either $s_v$ or $s_x$ exists. This means $uv^2wx^2y$ is not in $L$.

Since we can always pump $z$ outside of $L$, $L$ does not satisfy the pumping lemma. So, $L$ cannot be context-free.

I can assume that v or y are only in first part $u$ or second $v$ or $w$
but also $vxy$ can be in between $a's$ and $b's$ including the $\#$ between them.

I don't quite understand your statement literally.
However, apparently, you wanted to say that given $z$, there are various possibilities for $u$, $v$, $w$, $x$ and $y$, which is totally true. Only the usage of some abstraction or general property (which might be simple or complicated) will enable us to cover all of them. That is where the fun or wisdom are.


Will Java's hashCode() reduce collisions regardless of table size? for a class project we have to count the number of collisions from inserting words from a plaintext document into a hashtable. I read that using prime numbers for table sizes can offset the collisions resulting from a poor hashing function.

Do I have to create a poor hashing function to demonstrate the effects of table sizes on collision? Right now I am using Java's native hashCode() method as the key and am passing it into a hashing function to get the index. I passed the generated hashCode into variations of hashing functions, but found no difference in # of collisions between prime/non-prime table sizes.

//Hashing function
    scale = rand.nextInt(prime−1) + 1;
    shift = rand.nextInt(prime);
    private int hashValue(K key) {
                return (int) ((Math.abs(key.hashCode()*scale + shift) % prime) }

I also implemented quadratic probing, but my book says it should result in more collisions if the table size is non-prime.. I would really appreciate your advice.

Java's default implementation for hashCode() is probably doing quite a good job. If you were designing (or implementing) a language then you'd want to design your hashing function perform well. So yes, you should be generating your own hash codes.

If hash codes are more-or-less random (as they should be) then table size does not matter at all. Table size only starts to matter when the hash function is poor.

Suppose that, by some fluke, your hash function only output even numbers. Then, if the table size also were even, you'd only ever use half of the slots in your table (the even ones) - more than doubling the collision rate.

Now suppose that, all hash codes are $1$ modulo $3$. If your table size is a multiple of three, then you'd only ever use slots that are $1$ modulo $3$, cutting the effective size of your table by third.

The reason you want to pick a prime as table size is that this avoids any issues with poor hash functions (unless your hash codes all happen to be the same modulo that prime). On the other hand, picking $223092870$ as table size is a terrible idea.


Time complexity of finding subsequences of a string segmented into parts Let $S$ be a string of length $N$, consisting of digits 0 to 9.
For convenience, we assume $N$ to be a multiple of 3.

Then, we split $S$ into $N/3$ equal parts, each of length 3.

For each equal part, we count/enumerate all subsequences of all lengths up to 3.

Finally, we total up how many such subsequences are there altogether.

What is the time complexity of the above algorithm? Thanks.

I give a more concrete example in case the above is not clear. Suppose $S=`111211'$, of length 6.

We first split it into 2 parts $`111'$ and $`211'$. For the first part $`111'$, we  count that there are 3 subsequences of $`11'$ (note that subsequences do not have to be consecutive unlike substrings), for the $`211'$, there is 1 subsequence of $`11'$, so in total there are 4 subsequences of $`11'$. We do this for all possible subsequences up to length 3, even for subsequences that do not appear such as $'000'$, we count that it occurs zero times.

I am new to time complexity, but I did try to calculate it myself. For each part of length 3, the time complexity of enumerating the subsequences is $O(1)$? Hence, in total, we have to repeat it $N/3$ times, so the overall time complexity is $O(N)$?
Is that correct? Thanks a lot.


"NP-complete" optimization problems I am slightly confused by some terminology I have encountered regarding the complexity of optimization problems.  In an algorithms class, I had the large parsimony problem described as NP-complete.  However, I am not exactly sure what the term NP-complete means in the context of an optimization problem.  Does this just mean that the corresponding decision problem is NP-complete?  And does that mean that the optimization problem may in fact be harder (perhaps outside of NP)?

In particular, I am concerned about the fact that while an NP-complete decision problem is polynomial time verifiable, a solution to a corresponding optimization problem does not appear to be polynomial time verifiable.  Does that mean that the problem is not really in NP, or is polynomial time verifiability only a characteristic of NP decision problems?

An attempt on a partial answer:

Decision problems were already investigated for some time before optimization problems came into view, in the sense as they are treated from the approximation algorithms perspective.

You have to be careful when carrying over the concepts from decision problems. It can be done and a precise notion of NP-completeness for optimization problems can be given. Look at this answer. It is of course different from the NP-completeness for decision problems, but it is based on the sames ideas (reductions).

If you are faced with an optimization problem that doesn’t allow a verification with a feasible solution, then there is not much you can do. That is why one usually assumes that:

We can verify efficiently if the input is actually a valid instance of our optimization problem.
The size of the feasible solutions is bounded polynomially by the size of the inputs.
We can verify efficiently if a solution is a feasible solution of the input.
The value of a solution can be determined efficiently.

Otherwise, there is not much we can hope to achieve.

The complexity class $\mathrm{NP}$ only contains decisions problems per definition. So there aren’t any optimizations problems in it. And the Verifier-based definition of  $\mathrm{NP}$ you mention is specific to $\mathrm{NP}$. I haven’t encountered it with optimization problems.

If you want to verify that a solution is not just feasible, but also optimal, I would say that this is as hard as solving the original optimization problem because, in order to refute a given feasible and possibly optimal solution as non-optimal, you have to give a better solution, which might require you to find the true optimal solution.

But that doesn’t mean that the optimization problem is harder. See this answer, which depends of course on the precise definitions.


What's relation between Kolmogorov complexity and pseudorandomness? In a comment on this question, @Kaveh wondered whether the questioner really wanted to ask "is there a relation between strings with high Kolmogorov complexity and pseudorandomness?" This is not the question that was answered, in the end, but I would like to know the answer.

I understand that any pseudorandom sequence can be given a short description, by describing the program that generated it (as Travis M. points out in the question linked above).  So in one sense the sequence such a sequence does not have high Kolmogorov complexity.

On the other hand, it seems as if there's some connection between pseudorandomness and Kolmogorov complexity.  For if you didn't know the algorithm, then sequences generated by a good (passes lots of appropriate statistical tests, etc.) PRNG could not be described more briefly than by giving the sequence--on average, at least.  Right?  That's implicit in the kind of tests that good PRNGs have to pass: The tests are meant to rule out cycles and other regular patterns.  (We can also require that the PRNG be cryptographically secure, if that helps.)

Happy to be told that I'm hopelessly confused.  Just point me in the right direction.

The standard notion of pseudorandomness is about a process.  You can say that the process (the pseudorandom generator) is pseudorandom, or not.  The notion of pseudorandomness of a single string is not defined; that's not something you can talk about.

Kolmogorov randomness is a property of a bit-string.  You can say that a particular bit-string (sequence) is Kolmogorov-random, or not.  Effectively, a bit-string is Kolmogorov-random if it has high Kolmogorov complexity, i.e., there's no program that outputs that string that's shorter than the string itself.

If you have a pseudorandom generator, then the strings it outputs are never Kolmogorov-random.  Any output from the pseudorandom generator can always be generated by a short program (a program that hardcodes the seed to the pseudorandom generator, as well as the code of the pseudorandom generator itself), so isn't Kolmogorov-random.

That's the relationship.

Incidentally, Kolmogorov-random is not about knowledge of a program to generate the string.   Knowledge is irrelevant.  What matters is existence: whether or not exists a program that generates the string.  If there exists a short program that generates the string, then the string is not Kolmogorov-random -- and this remains true even if you don't know the program, or even if it would be difficult to find the program.

You asked about compressibility.  Let $G$ be a pseudorandom generator (in the standard cryptographic sense, i.e., computationally indistinguishable from true-random).  There is a sense in which outputs of $G$ are compressible, and a sense in which they are not.

The outputs of $G$ are compressible, if you don't care how long the compression algorithm takes to run.  Given $G$, we can construct a compression algorithm $C$ that compresses outputs from $G$ to something much shorter.  The catch is that $C$ takes a very long time to run: it takes exponential time.  In particular, $C$ works by exhaustively trying all possible seeds to see which is correct, and outputting the correct one.  This isn't of much relevance in practice -- an algorithm whose running time exceeds the predicted lifetime of the solar system isn't of much engineering relevance -- but it does demonstrate that the outputs of $G$ are Kolmogorov-compressible and thus aren't Kolmogorov-random.

Outputs of $G$ are not compressible (with high probability), if you limit the compression algorithm's running time to something reasonable.  For instance, suppose we limit $C$ to run in polynomial time, but allow $C$ to be otherwise unrestricted; then with high probability, running $C$ on the output of $G$ will not lead to any appreciable compression.  (Why?  Truly random bit-strings are, with high probability, not compressible by $C$.  If pseudorandom outputs from $G$ were compressible, then you would obtain a polynomial-time algorithm for distinguishing outputs of $G$ from truly-random strings, which is exactly what the definition of pseudorandomness promises cannot happen.)  So in practice, outputs of a pseudorandom generator are not compressible.

Maybe this helps enlighten the connection and contrast between standard pseudorandomness and Kolmogorov-randomness.  Standard pseudorandomness is about fooling a fast distinguisher (say, one that runs in polynomial time).  Kolmogorov-randomness is about fooling a short distinguisher (one whose source code is shorter than the pseudorandom string).  "Fast" is largely orthogonal to "short"; you can have a short program that is very slow (e.g., exponential running time), and you can have a long program that is still fairly efficient (its source code is longer than the input string, but its running time is at most polynomial in the length of that string).


Question about 'Software Transactional Memory' by Shavit and Touitou I've been reading the paper Software Transactional Memory by Shavit and Touitou. I understand how STM works in general but I need to understand this paper as it is the founding paper of the concept. However, I'm missing something rather fundamental of transactions. When I reed through the paper I never see what happens when a transaction fails. In general STM should retry a transaction when it fails, until it succeeds.

What the paper proposes is the following:

When a transaction starts it acquires the ownership of all the memory locations. Next, it computes the new values of each memory reference and writes them back to global memory. Finally, the transaction releases the ownerships. The transaction has succeeded and returns "success".

If a transaction tries to acquire ownership of a memory reference that is already owned by another transaction it will "help" this transaction by  running the same transaction. But only if the owning transaction is not in the failed state or success state.

A transaction goes into the success state when it has successfully acquired all the locks. It goes into the failed state when

But, nowhere in the paper can I find something about retrying a transaction?

For example, I have applied the pseudocode in the text to this scenario:

Suppose a transaction T1 that wants to run on dataset [A, B, C] and a transaction T2 that wants to run on dataset [C, D, E]. No other transactions are running in the system.

In order of execution:

T1 successfully acquires the locks for A, B and C
T1 now has the state success because it acquired all the ownerships.
T2 wants to acquire the locks for C, D and E.
T2 can not acquire the lock for C.
T2 its status changes to Failure
T2 releases all the ownerships it had (none at the moment)
T2 knows that C is the reference that caused the failure.
T2 executes the same transaction as the process that owns C.
T2 notices that T1 already is in the success state so it aborts.
T1 safely executes its transactions and commits the changes to the global memory

So nowhere in this scenario is T1 executed again?

Any insights are greatly appreciated!

So nowhere in this scenario is T1 executed again?

"Retry" is not among the main topics of the classic STM paper.

You can let the initiator of $T_1$ call StartTransaction() (treat $T_1$ as a new transaction) upon each Failure until it receives a Success. The authors have just ignored it probably because they want to focus on the ingenious STM concept.

Retry is of course a big topic itself, for instance, in Composable Memory Transactions.


Group testing puzzle I have a cake with $n$ layers in total. I know that $k$ are vanilla, and at least $n-k$ are not. I dislike all flavors other than vanilla, so I decide to only eat those layers.
I can't tell which layer is which flavor, but I can smell the vanilla. For any $m$ with $1\le m\le n$, I can test the top $m$ layers of the cake by removing them from the cake and taking them to another room. There, I can smell whether any of those layers are vanilla. Then I can replace those $m$ layers in their proper position on top of the cake.
Once I've performed enough tests to determine if a layer is vanilla, I eat it right out from the middle of the cake, leaving the $n-1$ layers intact. I need to be certain what I eat is vanilla. Then I can return to doing more tests to find the next vanilla layer.
How can I write an algorithm that takes in $n$
and $k$, and outputs the number of tests required to identify (and therefore eat) all of
the vanilla layers?

In my opinion, the only way we can do this is by checking every single layer individually... I don't see how taking multiple layers at a time would ever work.
Let vanilla = 1 and other flavors = 0.
Let's say we have a cake 011:
and we take 3 at a time, and find there is vanilla, then we anyways need to check every layer.
Let's say we have 0000001
and we take 3 layers, then yes, we can move on to the next 3. But why don't we take 4 or 5?
Or 7? if we take 7 though, we'd be back at the first issue.
I think we have to do this individually (it would take $n$ tests) because trying to shorten it simply does not give us enough information. Any clarification would be helpful as this does seem too simple to me!

Try to think in terms of binary search:
Start by checking half the cake. Then, if you didn't smell vanilla, you can be sure the first half does not contain vanilla, hence we don't need to check them anymore - hence we save time. This was only intuiton to why it might be possible to do better than $O(n)$, not the actual solution for it.
But something important to note is that any algorithm better than $O(n)$ must depend on $k$. Its not hard to show a lower bound of $\Omega(k)$


How to find max margin for non-separable SVM? I am new to Machine Learning. Suppose a training set of positive (square) and negative (circle) points is given like:

Obviously there would be no nice linear separator of positive and negative points. So assume there exist a transformation for (x1,x2) points as:
y1 = (x1-5)^2, y2 = (x2-5)^2 in (y1,y2) space. We will then map all positive points to (25,25) and all negative points to (1,1).

Now, the question is how can I find the maximum-margin separator in new space? That is, what curve in the original space transforms to the straight-line boundary in the transformed space? Using that I need to determine that should a new point be considered positive or negative.

Map all the points to the new space.  Then find the maximum-margin linear separator of those mapped points.  Algorithms for finding a maximum-largin linear separator are described in the literature on SVMs (that's exactly what you need to do to train a linear SVM).  In other words, you can map the points to the new space, then can take those mapped points and train a linear SVM on them.  That's conceptually how to do it.

In practice, nonlinear SVMs use clever tricks to do the same thing, but do it faster (using the kernel trick).


Why is the halting problem unsolvable by a turing machine? So my knowledge of CS is amateurish at best but to me, logically, it seems like the halting problem is solvable.

So any human can determine if a problem halts with rigorous inspection, so why can't a very advanced, say human AI, solve the halting problem?

Also, is there a machine, say more powerful than a turing machine, that can solve this problem?

PS: I might be making some bad assumptions, please point that out if so.

It can be proved that the halting problem cannot be solved by any Turing machine. There are several question regarding this on this side which you can look up.

It is not true that humans can determine if a given Turing machine halts. For example, we have been unable so far to compute many values of busy beaver functions, which measure the maximal number of steps a halting Turing machine can run given the number of tape symbols and number of states.

According to the Church–Turing thesis, every machine can be simulated by a Turing machine. So DNA computers, quantum computers and the like will not help. All they can do (especially the latter) is to dramatically speed up computation, but they cannot help computing non-computable functions.

There is a field known as hyper-computation which studies machines stronger than Turing machines, but these are not believed to be realizable by most practitioners. Recursion theory explores such models from a more theoretical perspective.


Minimize cost and maximize quality of function in four variables Problem: Find optimal values for four parameters which are used to tune an algorithm under the constraints of accuracy, time and memory.

I have an indexing scheme used to search for the K-nearest neighbors of a point in many dimensions. This indexing scheme has four adjustable parameters. For each given fixed problem size (total number of points, number of nearest neighbors to find, number of dimensions, desired accuracy) I plan to run a solver to find the optimal values for these four parameters. Here are the constraints:

1) If the accuracy is below desired accuracy (say 95%), prefer parameter values that maximize the accuracy.

2) Once the accuracy equals or exceeds the desired accuracy, prefer parameters that minimize the execution time.

3) Do not exhaust all system memory.

I handle #3 by restricting the one parameter that is directly proportional to memory usage based on numerous manual tests.

One of the parameters is discrete: it may only take on integer values. (This is the one that affects memory size).

Three of the parameters always move in the same direction as accuracy: as they increase, accuracy always remains the same or increases, up to a maximum of 100%. Each of these three parameters also moves in the same direction as cost: as they increase, the cost always increases (without bound).

The fourth parameter has the smallest (and least predictable) influence on cost. The accuracy will always decrease as you move farther away from the optimal value, either up or down.

Because of the 100% accuracy cutoff, the function has places with no derivative (is not smooth).

I have hundreds of combinations to optimize, varying # of dimensions versus # of points. My current approach runs all night without completing all the cases and produces erratic results (poor solver algorithm that gravitates toward high accuracy and horrible time cost). Given the nature of the constraints I have described and the number of parameters, which class of algorithms should I investigate? I understand the gradient method, but worry that it will perform poorly (too many steps) or not work with the non-smoothness of the function.

It might be possible to seed each successively larger case with the best results from the next smaller case; the parameter values should vary smoothly as the case sizes increase. the cost of evaluating the execution time and accuracy increases with the number of points and with the number of dimensions.

Current algorithm:

1) Start with seed values for each parameter, as determined after days of manual testing.

2) Holding all parameters fixed but one and varying that one, find its best value. Test values in increasing order, stopping when the accuracy is acceptable.

3) Repeat for all parameters.

4) Make five passes over all parameters. At each pass, use a finer grid for the search.

My approach is basically using an inefficient gradient search in one dimension at a time. It is slow and produces good results for the smaller cases but soon yields poor results for the medium sized cases.

The Four adjustable parameters

In thinking about them, I have decided that three of the parameters can be represented as discrete integer values, and only one is continuous.

a) Perms = Number of permutations of the index to create. Each index takes up  memory. This parameter has the dominant influence on memory usage. This ranges from 3 to 20. Depending on the number of points indexed, somewhere between 20 and 32 indices will use up all memory.

b) Margin = Number of points to select in each index probe. If K is the number of neighbors sought, Margin typically varies from 3*K to 20*K.

c) Box-Points = Number of random  faces of a hypercube surrounding the search point to probe. This ranges from 1 to 2*dimensions.

d) Box-Size = A fraction to multiply by the characteristic hypercube size to define the volume of hyperspace to search. Typically ranges from 0.3 to 1.5.

So, simplifying a bit, you want to maximize an objective function $\Phi(w,x,y,z)$, where $\Phi$ has the following properties:

$\Phi(w,x,y,z)$ is monotonically increasing in $w$, in $x$, and in $y$
for any fixed $w,x,y$, $\Phi(w,x,y,z)$ is monotonically increasing-then-decreasing in $z$, i.e., there exists some $z_0$ such that $\Phi(w,x,y,z)$ is monotonically increasing in $z$ for $z \le z_0$ and is monotonically decreasing in $z$ for $z \ge z_0$.

Here $\Phi(w,x,y,z)$ represents the accuracy.

There are efficient algorithms to maximize this objective function, if $\Phi$ has some additional nice properties.  I'll describe how to do so, in several steps.

Given $w,x,y$, it is possible to efficiently find the $z$ that maximizes $\Phi(w,x,y,z)$ using ternary search (see also here).  Let $\Phi_3(w,x,y)$ denote the value of $\Phi(w,x,y,z)$ for the value of $z$ that maximizes  $\Phi(w,x,y,z)$, i.e.,

$$\Phi_3(w,x,y) = \max_z \Phi(w,x,y,z).$$

The comment above indicates that you can efficiently compute $\Phi_3(w,x,y)$ using ternary search.  If $z$ comes from a discrete space with $N$ possible values, the running time to compute $\Phi_3(w,x,y)$ will be $\Theta(N)$; if it comes from a continuous space, you can find the approximate value of $\Phi_3(w,x,y)$, and for typical functions, it the convergence rate will often be very fast (the number of iterations will be proportional to the number of digits of accuracy you want in the answer).

Now, if we are lucky, $\Phi_3$ will be monotonically increasing in $w,x,y$.  If this happens, we can continue to apply a similar idea, as follows.

Under this condition, given $w,x$, it is possible to efficiently find the $y$ that maximizes $\Phi_3(w,x,y)$.  How?  Use binary search on $y$, and use the fact that we know how to efficiently compute $\Phi_3(w,x,y)$.  So, define

$$\Phi_2(w,x) = \max_y \Phi_3(w,x,y),$$

and note that this gives us an efficient way to compute $\Phi_2(w,x)$.  The running time will again be efficient, i.e., $\Theta(\lg N)$ evaluations of $\Phi_3$ if $y$ comes from a discrete space with $N$ possible values, otherwise we can get an approximate optimal value efficiently (typically, the number of evaluations of $\Phi_3$ needed is proportional to the number of digits of accuracy we want in the answer).

Suppose that $\Phi_2(w,x)$ is monotonically increasing in $w,x$ and $\Phi_1(w) = \max_x \Phi_2(w,x)$ is monotonically increasing in $w$.  Then Applying the same techniques, we can see that given $w$ it is possible to efficiently find the $x$ that maximizes $\Phi_2(w,x)$ (using binary search), and thus that it is possible to find the $w$ that maximizes $\Phi_1(w)$. Finally, the maximum value of $\Phi_1(w)$ is exactly the maximum value of $\Phi(w,x,y,z)$ over all $w,x,y,z$.

So if $\Phi$ has some additional nice properties, there are efficient algorithms.  The resulting algorithm will have running time $O(k^4)$, where $k = \lg N$ if each parameter comes from a discrete space; or where $k$ is typically proportional to the number of bits of accuracy desired if the parameter comes from a continuous space.

Therefore I suggest you try this and see if your $\Phi$ has the required nice properties.  If it does, you are in good shape and you can try a technique based on this.

What do you do if $\Phi$ doesn't have these nice properties?  Probably your best next bet is to try some standard black-box mathematical optimization routine, e.g., hill-climbing, gradient descent, or convex optimization.  If $\Phi$ is a relatively smooth function, I suspect they might work pretty well.


How can segment be 60KB I read that each segment is 64KB,but how?
If you have address ABCD:EFGH , then 1 segment is 16B if it is addreses by bytes.
How do they don't overlap?
Example:
 0000:0010 = 00010
 0001:0000 = 00010 , is is same address.

In "real mode" on the x86, an address is 32 bits long. The higher 16 bits can be considered the segment address, while the lower 16 bits are the address within the segment. But it's a bit more complicated than having $2^{16}$ segments of $2^{16}$ addresses each.

If you have a 16-bit address, then you're able to address $2^{16} = 65,536$ different locations. If each of those is a byte, you have 65,536 bytes, or 64KB, of addressable memory. So a segment is at most 64KB long.

To get the actual address, the segment address is effectively shifted left by four bits, then added to the address within the segment. This does, as you've noted, mean that the addresses are not unique! The address 0x0000.00FF is the same as the address 0x000F.000F in this system. Segments can, and frequently do, overlap. And this isn't considered a problem, because in "real mode", there's no protection whatsoever. Segments are just a convenience; the CPU doesn't care if you want to write to opposite ends of memory in completely different segments.

This also limits the total amount of addressable memory to $2^{20}$ bytes, rather than the $2^{32}$ you would expect with an address of that length. But this is also by design: the 8086 has only 20 address pins. So despite the apparent clumsiness of this system, it ended up working out well.


To prove Turing-completeness, is it enough to prove capability of producing arbitrary output? Turing completness is being typically proved via reduction to already proved Turing-complete machine.

Can the same be obtained by showing, that the machine in question is capable of generating arbitrary output – if proper input is given?

Turing-completeness means that the machine model in question can compute everything that is computable. That means that for every computable function $f$, there is a corresponding program for your model which behaves "like" $f$, where I put the quotes since the input and output may look differently.

Showing that the machine can generate arbitrary output is hardly enough - consider the machine model which executes only one program, copying its input to its output.


Resolving ambiguity in dangling else Initially the ambiguous grammar is as follows (with some cropped production rules):

<STMT>         -->  <IF-THEN> | <IF-THEN-ELSE>
<IF-THEN>      -->  if condition then <STMT>
<IF-THEN-ELSE> -->  if condition then <STMT> else <STMT>

To resolve the ambiguity, the previous grammar is transformed into the following one in the book I study:

<STMT>           -->  <IF-THEN> | <IF-THEN-ELSE>
<IF-THEN>        -->  if condition then <STMT>
<IF-THEN-ELSE>   -->  if condition then <E-STMT> else <STMT>
<E-STMT>         -->  <E-IF-THEN-ELSE>
<E-IF-THEN-ELSE> -->  if condition then <E-STMT> else <E-STMT>

What I cannot get is that why the following rule is necessary.

<E-IF-THEN-ELSE> -->  if condition then <E-STMT> else <E-STMT>

As far as I think about, the update on <IF-THEN-ELSE> and introduction of <E-STMT> is sufficient to resolve the ambiguity. Could you please give an example refuting my argument? Thanks..

I assume that one can also derive some atomic statements from <STMT> and <E-STMT>, otherwise the language of both grammars would be empty and all would be quite trivial. :-) But that aside:

The new grammar should do two things: it should be unambiguous and it should generate the same language.

The variables <E-STMT> and <E-IF-THEN-ELSE> are introduced to remember part of the context in which the variable occurs. What you want to accomplish, is that the variables <STMT>, <IF-THEN> and <IF-THEN-ELSE> cannot occur in a position directly preceeding an else symbol, and also that the variables <E-STMT> and <E-IF-THEN-ELSE> must occur in a position directly preceeding an else symbol. So, if we see a <E-STMT> or <E-IF-THEN-ELSE> somewhere, we know that the next symbol must be else, and if we see an other variable we know that the next symbol cannot be an else. This way we have some week form of "context-awareness".

If we remove the rule for <E-IF-THEN-ELSE> and replace the rule for <E-STMT> by

<E-STMT> -> <IF-THEN-ELSE>

then we can derive the following:

  <STMT> $\to$
  <IF-THEN-ELSE> $\to$
  if condition then <E-STMT> else <STMT> $\to$
  if condition then <E-IF-THEN-ELSE> else <STMT> $\to$
  if condition then if condition then <E-STMT> else <STMT> else <STMT>

and here a <STMT> variable which directly preceeds an else symbol. This will lead to ambiguities.

If we try to fix this and additionally change the if-then-else rule to

<IF-THEN-ELSE> --> if condition then <E-STMT> else <E-STMT>

then we can perform the derivation

  <STMT> $\to$ <IF-THEN-ELSE> $\to$ if condition then <E-STMT> else <E-STMT>

and here we have an <E-STMT> variable without a following else symbol. Since the <E-STMT> generates no if statements without else clause, the language of the new grammar is not the same.

The grammar which was proposed in the book solves both these problems.


Find set of non-overlapping rectangles in a 2D grid I have a $n \times m$ rectangular grid of cells, and a set $R$ of rectangles within this grid.  Each rectangle is a subset of the cells.  (Alternatively, you can think of them as axis-aligned rectangles where each of the four corners has integer coordinates.)

I want to find a subset $S$ of rectangles, so that $S \subseteq R$, so that no two rectangles in $S$ overlap, and so that $S$ is as large as possible.  (Alternatively, you can think of this as finding a maximum independent set in a graph where we have one vertex per rectangle, and an edge between two rectangles if they overlap.)

Can this problem be solved in polynomial time?  Is it NP-hard?

I can see how to solve the one-dimensional analog (maximum set of non-overlapping intervals) in polynomial time using dynamic programming, but that algorithm doesn't seem to extend to this case.  Wikipedia calls this the maximum disjoint set problem and says that when the set of shapes is arbitrary, the problem is NP-hard, but it doesn't discuss the specific case of axis-aligned rectangles with integer coordinates.  That makes me suspect this problem might be NP-hard, but I haven't found a reference or proof of that.

The problem you state is shown to be NP-Hard [1, 2]. However, there is an $O(\log \log n)$ approximation algorithm for the problem [3].

[1] H. Imai, T. Asano. Finding the Connected Components and a Maximum Clique of an Intersection Graph of Rectangles in the Plane. Journal of Algorithms 4(4): 310-323, 1983.

[2] R.J. Fowler, M.S. Paterson and S.L. Tanimoto, Optimal packing and covering in the plane are NPcomplete. Information Processing Letter. 12 3 (1981), pp. 133137.

[3] Parinya Chalermsook, Julia Chuzhoy: Maximum independent set of rectangles. SODA 2009: 892-901


Generating Combinations from a set of pairs without repetition of elements I have a set of pairs. Each pair is of the form (x,y) such that x,y belong to integers from the range [0,n).

So, if the n is 4, then I have the following pairs:

(0,1) (0,2) (0,3)
(1,2) (1,3)
(2,3)

I already have the pairs. Now, I have to build a combination using n/2 pairs such that none of the integers are repeated (in other words, each integer appears at least once in the final combination). Following are the examples of a correct and an incorrect combination for better understanding

 1. (0,1)(1,2) [Invalid as 3 does not occur anywhere]
 2. (0,2)(1,3) [Correct]
 3. (1,3)(0,2) [Same as 2]

Can someone suggest me a way to generate all possible combinations, once I have the pairs.

One direct way is a recursive procedure that does the following on each invocation. The input to the procedure is a list of pairs that have already been chosen and a list of all the pairs.

Compute the smallest number not already covered by the input list. For the first invocation, this will be 0 of course, because no pairs have been chosen.
If all the numbers are covered, you have a correct combination, print it out and return the the previous step. Otherwise, the smallest number that is uncovered is the target we will aim for.
Search through the pairs looking for a way to cover the target number. If there is none, then just return to the previous level of recursion.
If there is a way to cover the target number, pick the first way and recursively call the entire procedure again, with the pair just picked add to the list of chosen pairs.
When that returns, look for the next way to cover the target number with a pair, without overlapping a previously chosen pair. If you find one, pick it and again recursively call the next procedure.
Continue steps 4 and 5 until there are no more ways to cover the target number. Go through the entire list of pairs. When there are no more correct choices, return to the previous level of the recursion.

The way to visualize this algorithm is with a tree whose paths are sequences of non-overlapping pairs. The first level of the tree contains all the pairs that contain 0. For the example above, the tree is

           Root
             |
     ----------------
     |       |       |
   (0,1)   (0,2)   (0,3)
     |       |       |
   (2,3)   (1,3)   (1,2)

In this example all the paths through the tree actually give correct collections, but for example if we left out the pair (1,2) then the rightmost path would have only one node and would correspond to the search in step 3 failing.

Search algorithms of this type can be developed for many similar problems of enumerating all objects of a particular type.

It was suggested that perhaps the OP meant that all pairs are in the input, not just a set of them as the question says. In that case the algorithm is much easier because it's no longer necessary to check which pairs are allowed. It's not even necessary to generate the set of all pairs; the following pseudocode will do what the OP asked. Here $n$ is the input number, "list" starts out as an empty list, and "covered" is an array of length $n$ initialized to 0.  It could be made somewhat more efficient but that's not my immediate goal.

sub cover {
  i = 0;
  while ( (i < n) && (covered[i] == 1 )) {
   i++;
  }
  if ( i == n ) { print list; return;}
  covered[i] = 1;
  for ( j = 0; j < n; j++ ) {
    if ( covered[j] == 0 ) {
      covered[j] = 1;
      push list, [i,j];
      cover();
      pop list;
      covered[j] = 0;
    }
  }
  covered[i] = 0;
}


Heuristic for sokoban puzzle problem I am trying to write IDA* for Sokoban puzzle problem (http://en.wikipedia.org/wiki/Sokoban) but It seems that my heuristic is not so good for making the algorithm fast.

My heuristic is to consider $h(s)$ as minimum  distance between the Player and Boxes plus minimum distance between a Box and a Target in state $s$.

Can you please provide some better heuristics for this problem?

Edit: consider the number of Boxes(and Targets) is at most 3!

Hi there CoderInNetwork,

That ain't an easy question and any advances regarding a good heuristic function would be very welcome. Indeed, I will refer in my answer to Andreas Junghanns' PhD written in 1999 (yeap, 16 years ago and still the current state of the art in the field). You can find it in citeseer:

Andreas Junghanns' PhD

Go to Section 4 and you will see a discussion about a heuristic function. The easiest one comes from a simple observation: every stone has to go to one and only one target location so you have to solve a minimum cost perfect matching in a bipartite graph where one set of vertices is made of the stones and the other one is made of the target locations ---so that there are obviously edges going only from the first set to the second and the goal is to find the minimum assignment of stones to goals. The cost of every edge would be equal to the estimated distance to get to the goal assigned from every stone.

This can be done in $O(n^3\log_{2+\frac{n}{4}}n)$ using minimum cost augmentation ---again refer to Andreass Junghanns' PhD, Section 4.3.3 in page 52.

Even considering that this heuristic can be computed in an acceptable time (after making a good number of code optimizations) note that it does not account for dead locks. This is, it will naively move the stones without considering that either the walls or other stones can lead to unsolvable configurations.

From this observation, Andreas Junghanns introduced the idea of using Pattern Databases (PDBs) for improving this lower bound (see a discussion of their implementation in Chapter 5). At the time of writing his PhD, PDBs were not very well known but they are quite well known nowadays and a lot of progress has been made.

Finally, regarding your question: even if there are only 3 stones, problems can be really difficult to solve (or, at least, to solve optimally if that's what you are aiming for). See Appendix B, page 158, The 61 Kids Problems and you'll see lots of challenging problems. Many of those contain only 3 stones.

Hope this helps,


How does Stack Inspection work? This is precursor to my other, more advanced question about Stack Inspection.

Stack Inspection is a security mechanism introduced in the JVM to deal with running code originating from locations having different levels of trust. This is question aims at finding a simple description of its functionality. So:

  How does stack inspection work?

See

"Understanding Java Stack Inspection" by D. S. Wallach and E. W. Felten (1998)

From the paper:

... The stack inspection algorithm used in current Java systems
can be thought of as a generalization of the following simple
stack inspection model:

In this model, the only principals are “system” and “untrusted”. Likewise,
the only privilege available is “full.” This model
resembles the stack inspection system used internally in
Netscape Navigator 3.0.

In this model, every stack frame is labeled with a principal
(“system” if the frame is executing code that is part of
the virtual machine or its built-in libraries, and “untrusted”
otherwise), and contains a privilege flag which may be set
by a system class which chooses to “enable its privileges,”
explicitly stating that it wants to do something dangerous.
An untrusted class cannot set its privilege flag. When a
stack frame exits, its privilege flag (if any) automatically
disappears.

All procedures about to perform a dangerous operation
such as accessing the file system or network first apply a
stack inspection algorithm to decide whether access is allowed.
The stack inspection algorithmsearches the frames
on the caller’s stack in sequence, from newest to oldest.
The search terminates, allowing access, upon finding a
stack frame with a privilege flag. The search also terminates,
forbidding access and throwing an exception, upon
finding an untrusted stack frame (which could never have
gotten a privilege flag). ...

and the book "Securing Java" (in particular chapter three also available online)


Is there a mapping reduction for every two language $A$ and $B$ to some language $C$? One of my friend told me that there is a language $C$ for every two languages $A$ and $B$ s.t $A \leq_{m} C$ and $B \leq_{m} C$ , he simply define two languages $A’=\{0w|w \in A\}$ and $B’=\{1w|w \in B\}$ so $C=A’ \cup B’$ and he define the function $f(w)=0w$ if $w \in A$ and and $f(w)=1w$ otherwise. I suspect this function is turing-computable. Suppose $A$ be $\overline{HP}$ which is not RE. How we can decide if $w \in A$ ? Even i ask myself can we realy prove that such a mapp-reduction always exist ?

The definition of the reduction is wrong.
We actually need to define two reductions: from $A$ to $C$ and from $B$ to $C$. The reduction from $A$ to $C$ maps $w$ to $0w$. The reduction from $B$ to $C$ maps $w$ to $1w$.


Why is Quicksort described as "in-place" if the sublists take up quite a bit of memory? Surely only something like bubble sort is in-place? Quicksort is described as "in-place" but using an implementation such as:

def sort(array):
    less = []
    equal = []
    greater = []
    if len(array) > 1:
        pivot = array[0]
        for x in array:
            if x < pivot:
                less.append(x)
            if x == pivot:
                equal.append(x)
            if x > pivot:
                greater.append(x)
        return sort(less) + equal + sort(greater)
    else:
        return array

You have to create a copy of the list for each recursion. By the first return, in memory we have:

array
greater+equal+less

Then by the second recursion across all sub-lists we have:

array
greater, equal, less from first recursion
greater+equal+less from less1, greater+equal+less from greater1

etc...

Is this just badly written code or am I correct in thinking that for a big list, you actually have to have, proportionally, a fair amount of extra space to store thse?

When I think of something that is "in-place", I think of bubble sort, which simply swaps elements in the list like: http://en.wikipedia.org/wiki/File:Bubble-sort-example-300px.gif

BubbleSort only requires 1 extra variable to store a potentially swapped element.

This particular implementation of quicksort is not in-place. It treats the data structure as a list that can only grow in one direction (in which case a merge sort would be simpler and faster). However, it is possible to write an in-place implementation of quicksort, and this is the way it is usually presented.

In an in-place implementation, instead the sort function is not called recursively on newly constructed arrays that become smaller and smaller, but on bounds that become closer and closer.

def sort(array, start, end):
    if end >= start: return
    pivot = array[start]
    middle = start + 1
    for i in range(start+1, end):
        if array[i] >= array[middle]:
            tmp = array[i]
            array[i] = array[middle]
            array[middle] = tmp
            middle += 1
    sort(array, start, middle)
    sort(array, middle, end)

(Beware of this code, I have only typed it, not proved it. Any off-by-one errors are yours to fix. Real-world implementations would use a different algorithm for small sizes but this doesn't affect asymptotic behavior. Real-world implementations would choose a better pivot but I won't get into that here as it doesn't really for this question.)

The Wikipedia page presents both a non-in-place and an in-place version of the algorithm.

Quicksort as written here requires $O(d) + s$ extra storage, where $d$ is the depth of the recursion (which depends on the pivot quality) and $s$ is the element size. The stack size requirement can be improved: there are two recursive calls, and we can make the second one a tail call (which consumes no stack). If we always do the recursive call on the smaller half first, then the maximum stack size for array lengths up to $n$ satisfies $\hat S(n) \le \hat S(m)$ with $m \le n/2 \le \hat S(n/2)$, so $\hat S(n) \le \lg_2(n) \hat S(1)$. Thus we can achieve $O(\log n) + s$ extra storage requirement, regardless of the pivot choice.

There are plenty of other sorting algorithms that can be implemented in-place, including insertion sort, selection sort and heap sort. The simple form of merge sort isn't in-place, but there is a more sophisticated variant which is.

 Thanks to Aryabhata for pointing out that Quicksort can always be done in $\lg(n)$ stack and that there is a variant of merge sort with both $O(1)$ additional storage and $O(n \log(n))$ runtime.


Linear congruential generator with uniform distribution I am currently studying linear congruential generators, and there was an example in which I didn't get the code:

public class Random {

static final int a = 48271;
static final int p = 2147483647; //2^31 - 1
static final int q = p/a;
static final int r = p%a;
int state;

public Random() {
    this ( (int)(System.currentTimeMillis()%Integer.MAX_VALUE ));
}

public Random(int initialValue) {
    if (initialValue < 0)
        initialValue += p;
    state = initialValue;
    if (state == 0)
        state = 1;
}

public int randomInt() {
    int tmp = a * (state % q) - r * (state/q);  //line I don't get
    if (tmp < 0)
        state = tmp+p;
    else
        state = tmp;
    return state;
}
}

The teacher said that it was so that all numbers can be expressed in 32 bits (or somethig like that). The thing is that a LCG should have a period of exactly $p-1$ and I don't get why it should be the case with this line.

Could you also explain why the following code would not work?

public int randomInt() {
    int tmp = (a*state)%p;
    if (tmp <= 0) state = tmp+p;
    else state = tmp;
    return state;
}

Thanks in advance for any answer.

Edit: I compared both generators by generating numbers in the interval $]0,1[$ with the following codes:

    //Generators
    public int randomInt() {
        int tmp = (a*state)%p;
        if (tmp <= 0) state = tmp+p;
        else state = tmp;
        return state;
    }

    public int randomInt2() {
        int tmp = a * (state % q) - r * (state/q);
        if (tmp < 0) state = tmp+p;
        else state = tmp;
        return state;
    }

    public double randomReal() {
        return randomInt()/(double)p;
    }

    public double randomReal2() {
        return randomInt2()/(double)p;
    }

And the Main method:

import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileWriter;
import java.io.IOException;

public class Main {

public static void main(String[] args) {

    File file = new File("resultatsGC.xls");
    FileWriter fw = null;
    Random rand = new Random();
    Random rand2 = new Random();
    double x, y;
    int[] tab = {0,0,0,0,0,0,0,0,0,0};
    int[] taby = {0,0,0,0,0,0,0,0,0,0};

    try {

         for (int i = 1 ; i < Math.pow(2, 31)-1 ; i++) {
            x = rand.randomReal();
            y = rand2.randomReal2();
            for (int j = 0 ; j < 10 ; j++) {
                if (x > j/(double)10 && x < (j+1)/(double)10) {
                    tab[j]++;
                }
                if (y > j/(double)10 && y < (j+1)/(double)10) {
                    taby[j]++;
                }
            }
            if (i%100000000 == 0)
                System.out.println(i+") "+x);
        }

        fw = new FileWriter(file, false);

        //Write in file the results
        for (int i = 0 ; i < 10 ; i++) {
            double a = ((double)i)/10;
            double b = ((double)(i+1))/10;
            String str = "["+a+";"+b+"]\t";
            fw.write(str);
            fw.write(tab[i]+"\t");
            fw.write(taby[i]+"\n");
        }

        fw.close();

    } catch (FileNotFoundException e) {
        e.printStackTrace();
    } catch (IOException e) {
        e.printStackTrace();
    } finally {
        try {
            if (fw != null)
                fw.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
        System.out.println("DONE!");
    }
}
}

And here is what it graphically gives:

Orange columns are the results of the algorithm that I had a question about. Clearly, it is better (much more uniform), but my question remains: why is it correct (even more correct than the other)?

One issue with your generator is that when computing tmp = (a*state)%p, you are actually taking modulo twice: first modulo $2^{32}$ (with sign), then modulo $2^{31}-1$. So you aren't really computing $a^t \pmod{p}$ like you might have expected. To test this hypothesis, you can ask Java to use long for the multiplication a*state – the results should improve. There is also a difference between using signed and unsigned arithmetic, though you can't test this in Java.

The other generator is more careful - it's only multiplying small numbers (the result is below $2^{31}$), which is why the truncation issue doesn't effect it.

The other generator computes the function
$$ y\lfloor \tfrac{p}{a} \rfloor + z \mapsto az - (p\pmod{a}) y. $$
(The comparison to $0$ just ensures that the result is in $[0,p)$ without affecting the value modulo $p$.)

The idea is that
$$ a(y\lfloor \tfrac{p}{a} \rfloor + z) \equiv az + y(a\lfloor \tfrac{p}{a}\rfloor-p) \pmod{p}. $$
Now $a\lfloor\frac{p}{a}\rfloor-p = -(p\pmod{a})$, and so the other generator really computes $x \mapsto ax \pmod{p}$.


Non-erasing Turing machines and loss of generality A non-erasing Turing machine is one that cannot replace a symbol with a blank unless the symbol under the read head is a blank.  I'm trying to understand whether there is loss of generality because of this restriction.

My guess is that there is no loss of generality, because the restriction above merely restricts replacing characters with blanks, but we can just as easily replace them with some other symbol and construct any rules that might have used blanks to use the new symbol.  I think that's too simple a solution though.

Can anyone give me any insight as to how to show whether or not generality is lost in the special case of non-erasing Turing machines?

Your definition of non-erasing Turing machine is "not the common one". Turlough Neary nicely summarizes early definitions and results for non-erasing Turing machines:

  Non-erasing Turing machines are a restriction of Turing machines that are permitted to overwrite blank symbols only. Moore [Moo52] mentions that Shannon had proved that non-erasing Turing machines simulate Turing machines, however this result was never published. Shortly after, Shannon proved 2-symbol Turing machines universal, Wang [Wan57] proved 2-symbol non- erasing Turing machines universal. Later, Minsky [Min61] proved the same result as Wang using a different technique. Minsky proved 2-tape non- writing Turing machines were universal and showed 2-symbol non-erasing Turing machines simulate these non-writing machines.

So here it says "overwrite blank symbols only", while you wrote "cannot replace a symbol with a blank unless the symbol under the read head is a blank".

In general, it seems that being non-erasing is not a serious restriction, but the answer here has one reference with results that point in the opposite direction:

  John E. Hopcroft, Jeffrey D. Ullman, "Nonerasing Stack Automata". JCSS, 1(2):166–186, 1967.


If anything can be verified efficiently, must it be solvable efficiently on a Non-Deterministic machine? Suppose, I wanted to verify the solution to $2$^$3$. Which is $8$.

The $powers~of~2$ have only one 1-bit at the start of the binary-string.

Verify Solution Efficently

n = 8
N = 3
IF only ONE 1-bit at start of binary-string:
  IF total_0-bits == N:
   if n is a power_of_2:
     OUTPUT solution verified, 2^3 == 8

A solution will always be approximately $2$^$N$ digits. Its not possible for even a non-deterministic machine to arrive to a solution with $2$^$N$ digits faster than $2$^$N$ time.

Question

Can this problem be solved efficently in non-deterministic poly-time?
Why not if the solutions can be verified efficently?

You need to decide whether you want to talk in terms of decision problems (dealing with classes like $\textrm{P}$ or $\textrm{NP}$) or with function problems  (dealing with classes like $\textrm{FP}$ or $\textrm{FNP}$).

If you choose to talk in terms of decision problems, then the decision problem is to decide, given $(m, n)$, whether it is true that $m = 2^n$. This problem can indeed be solved (and thus verified) in polynomial time.

If you choose to talk in terms of function problems, then the problem is given $n$, compute $2^n$. This cannot be done in polynomial time, even with non-determinism, but just because the output is exponentially big with respect to the input. Verification has nothing to do here.


When inserting an element in a priority queue and the heap size is already at max capacity, should you output an error OR increase the array size? I'm currently learning about how to implement priority queues using heaps, but I've  hit a wall while trying to implement the insertion operation. Assume that the size of the array storing the elements of the heap is n, and the size of the heap is also n. Assume further that we try to insert an element 'x' inside the heap. We would have to increment the heap size by 1, but this would now make the heap size greater than the size of the array, which is unacceptable.

So my question is: how do we deal with this problem. Should we A: simply throw an error (since heap size == array size), or B: increase the size of the array by 1. A huge majority of the programs I've seen online implement A, but I think B would be better. Are there any advantages/disadvantages of using A over B (or vice versa)? Are there any other strategies to solving this problem?

Any help is greatly appreciated.

I decided to go with option B, as it seems like the more practical thing to do.


Maximal prefix codes and maximal length Let $X$ a maximal prefix code on an alphabet $A$, $m(X)$ its maximal length, $F = X \cap A^{m(X)}$ and $F’ \subseteq A^{m(X)}$. Let $X’ = X \setminus F \cup F’$ a maximal prefix code. Why is it true that $X’ = X$? In other words, why is it true that one cannot obtain a maximal prefix code from another maximal prefix code with same maximal length by changing only the words of maximal length? Any reference for this result?

I'll assume that a prefix code is a set of words in which no word is the prefix of any other, and "maximal" means it is impossible to add any word to the set and keep this property.
Let $w$ be a maximal-length word that is not in $X$. There are two possibilities:

At least one (shorter) word in $X \setminus F$ is a prefix of $w$, in which case we could not add $w$ even if we first remove all words in $F$ from $X$;
No (shorter) word in $X \setminus F$ is a prefix of $w$, in which case we could add $w$ to $X$ without needing to first remove any words in $F$, contradicting the assumption that $X$ is maximal.


Understanding $DSPACE(s(n)) \subseteq DTIME(2^{O(s(n))})$ I'm having trouble understanding this statement: $DSPACE(s(n)) \subseteq  DTIME(2^{O(s(n))})$.

The logic is that $2^{O(s(n))}$ is the total number of different configurations a Turing Machine M that runs in $s(n)$ space can have as a combination of the number of states, head positions, and contents of the tape, but I do not see how this number is arrived at.

Can someone explain?

Suppose that $M$ is a deterministic Turing machine that runs in space $s(n)$ and halts on all inputs. We show below that $M$ has $U(n) = 2^{O(s(n))}$ many configurations. I claim that if $M$ doesn't halt within $U(n)$ steps, then it never halts; since we assumed that $M$ always halts, this means that it always halts within $U(n)$ steps. To see the claim, let $\sigma_0,\ldots,\sigma_{U(n)}$ be the configurations after $0,\ldots,U(n)$ steps. Since there are only $U(n)$ different configurations but $U(n)+1$ many $\sigma_i$'s, there must be $i<j$ such that $\sigma_i = \sigma_j$. Therefore starting at $\sigma_i$, the machine will repeatedly go through the configurations $\sigma_i,\ldots,\sigma_{j-1}$, and in particular, will never halt.

It remains to count the number of configurations. Suppose that $M$ has $Q$ states, $C$ tapes, and tape alphabet $\Sigma$. We can describe a configuration of $M$ by specifying the state ($Q$ options), the head locations ($s(n)^C$), and the tape contents (at most $|\Sigma|^{Cs(n)}$; in these bounds we used the fact that at most $s(n)$ cells are used in each tape. In total, the number of configurations is at most
$$
U(n) = Q s(n)^C |\Sigma|^{Cs(n)}.
$$
You can show that $U(n) = 2^{O(s(n))}$ using standard manipulations, completing the proof.


Comparing asymptotics of various functions Is the first function big oh, theta or omega of the second function in the following examples.

$(\log n)^{\log n} $ and $ \frac{n}{\log n}$
I am not sure how fast the first function grows.

$n2^n$ and $3^n$
I think the second function grows faster but not sure how to prove it.

$(\log n)^{\log n} $ and $2^{(\log_2n)^2}$
This is just puzzling.

$\sum_{i=1 }^n i^k$ and $n^{k+1}$.
And so is this.

Any help is much appreciated.

For the first and the third, taking the logarithm of both sides will really help. For the second, try to use the fact that if $\lim_{n\to\infty} \frac{f(n)}{g(n)} = 0$ then $f(n) = o(g(n))$. For the fourth, try approximating the sum using an integral.


Regular language proving Question:The set of all first names given to children born in New Zealand in 1996

I think this language is regular because every element in the set can be a accept state

How can I prove if the language is regular?

Every finite language is regular. The easiest way to prove it is to build the regular expression $w_1+w_2+\dots+w_n$ where $\{w_1,\dots,w_n\}$ is you finite language.

You can also build an automaton as you said. May be build a separate one  for each word and the do a finite union is the easiest.


Voronoi Diagram: Exactly 2n-5 vertices I want to find some characteristics for a set of points $S$ which contains $n$ points and has some Voronoi Diagram $V(S)$. This diagram should have exactly $2n-5$ vertices.

I tried to use the Euler formula for planar graphs which says $v-e+f = 2$:

$\Rightarrow 2n -5 -e + n = 2 \Rightarrow e = 3n-7$ - but what can I now do with the information that $V(S)$ has $3n-7$ vertices?

You made a small mistake by thinking that the Voronoi diagram is a planar graph. Remember that it has those rays that go to infinity. you can make a planar graph out of the Voronoi diagram by adding a new vertex and making all rays incident to this "apex". Plugging this into Euler's formula yields

$$ 2n-4 - e + n = 2 \quad \Rightarrow \quad  e= 3n - 6.$$

A planar graph has $3n-6$ edges if it is a triangulation (this can als be obtained via Euler's formula – just set $3f=2e$). As a consequence the dual graph to your Voronoi diagram (the Delaunay tessellation) is a triangulation. Or phrased differently, every vertex of your Voronoi diagram  has degree~3 and there are three rays.


Algorithm for a 2D path-finding puzzle I am trying to find an algorithm for finding an optimal solution to a puzzle of a given format. The 7 by 6 puzzle board is made out of the following pieces:

The tears are as follows:

Tears and grommets can be rotated and moved around the board, but spools, tie-offs and blockers cannot.

A simple example of the puzzle in it's starting state is:

While a more complicated version and a possible solution is:

The puzzle is scored by how many pieces are used in the solution (more is better) and how quickly the puzzle is solved.

I have so far written functions to detect and read in the board, as well as a function to check that the board is valid.

In order to solve the board, I have so far tried a brute force method, which randomly shuffled and rotated the movable pieces in the puzzle and then checked if the result was a valid solution, but this was fairly slow even for the simple boards, and extremely slow for more complex boards, and of course, did not come up with an optimal solution.

I then refined it a bit by excluding obvious wrong piece placements, but this was still over a second for small boards, and anywhere from 5 to 30 seconds for larger boards, and was also not an optimal solution.

I have heard about possibly using various path finding algorithms such as Djikstra's or A* but I'm struggling to see how these algorithms can be used to find the longest valid path, especially when branching pieces such as the 'T' and '+' pieces come into play.

Any help would be much appreciated!

One approach would be to bring out the big hammer and try using a SAT solver.  You introduce boolean variables $x_{\ell,p,o}$, which is true if piece $p$ is placed in orientation $o$ in location $\ell$ on the grid.  Then, you write down boolean clauses to encode the conditions for a grid to be valid.  Finally, you do binary search: given $k$, you try to find a placement that has score at least $k$ (by writing boolean clauses to force the score to be at least $k$ and then using a SAT solver to test whether there exists an assignment to the variables that satisfies all of the clauses), and then do binary search on $k$.  This might be effective, or it might be slow; it's hard to predict, so the only way to find out is to try it.

The trickiest part of encoding into SAT will probably be calculating the score.  I suspect it will be useful to introduce extra boolean variables $y_{\ell}$, which is true if the piece at location $\ell$ is connected to the spool.  Then, write constraints that capture the relationship between the $x$'s and $y$'s.


How to proof UNIQUE-SAT is in $\Delta^p_2$ How to proof UNIQUE-SAT is in $\Delta^p_2$ or in $P^{sat}$

1) when given a bool formula can I ask oracle whether the given formula has at least one satisfying truth assignment and whether it has at least two?

2) Is UNIQUE-SAT in NP?

UNIQUE-SAT is complete for the complexity class US. It is not hard to reduce coSAT to UNIQUE-SAT (by adding a trivial satisfying assignment), and so if UNIQUE-SAT is in NP, it would imply that NP=coNP, which is considered unlikely. There is a randomized reduction from SAT to UNIQUE-SAT, which implies that UNIQUE-SAT∉P unless NP=RP.

A SAT oracle can only answer one type of question: is the given formula satisfiable or not. However, you can use it to answer other questions. For example, in order to determine whether there are at least two satisfying assignments for some formula $\varphi$, you can ask whether the following formula is satisfiable: $\varphi(x) \land \varphi(y) \land x \neq y$ (you can convert this into CNF).


If L1 ∪ L2 and L1 are regular, is L2 also regular? This is a problem in a theory of computation book that's stumping me:

  Suppose that we know that $L_1 ∪ L_2$ and $L_1$ are regular. Can we conclude that $L_2$ is
  regular? Explain.

At first, I thought I could build the NFA that is the union of two DFAs, one which accepts $L_1$, and one which we don't know about.  Then lambda transition over to the $L_1$ DFA.  Then, the union would be regular, but we wouldn't be able to conclude anything about the $L_2$ DFA.

I think my reasoning is poor though.  Could someone please point me in the right direction?

Thank you.

No, since $\Sigma^* \cup L$ and $\Sigma^*$ are regular languages, for any $L$ and there are non-regular languages, we cannot conclude anything about $L$.


Good motivation for parallel data structures and algorithms I have a more general question for you. I'm working in Parallel Data Structures and Parallel Algorithms. That is a nice topic with a lot of interesting challenges. However, I have some problem to argue for why is necessary use parallel solutions. The most common justification is "We need to take advantage of the current architectures", "Parallel alternatives speed up sequential alternatives", but it isn't enough. Some people can think: OK, I believe you, but I don't have any problem waiting 10 minutes for my efficient sequential algorithm instead of 2 minutes for your parallel algorithm. That reflects a weak spot of parallel solutions: they are, in general, difficult to program and need more time to debugging.

So, now I'm trying to find a better motivation for parallel solutions. I have this motivation now: There are problems that don't have efficient solutions in sequential, and parallel solutions appear like the best alternative for those kind of problems. My question now for you is: How characterize this kind of problems?. I thought in problems with a lot of computation, like some graph problems, but I would like to know other view points.

The quintessential example is large-scale physics simulations, say "electronic" wind tunnel or protein folding (i.e. "finding new medicines"). Both are hugely expensive in terms of computation cost, but yield themselves well to parallelization.

Another area in which parallelization is important is "big data", say search engines. When dealing with big data you need to divide the work among many processors. However often in these cases, most of the work is done in an "embarrassingly parallel" fashion, in which each processor does its share of work, and everything is combined in the end; you could (but don't have to) argue that this is not an interesting example for parallel algorithms.

Yet another example is computer animation, say for the movie industry. This example probably has the same shortcoming as the previous one.

What is common to all three examples is that computation is very costly, and cannot be executed sequentially within a reasonable span of time. Hence the need to distribute the work among several computers (or processors, or cores).

Another possible use case is when you want answers really fast. Here an example could be real-time cryptanalysis during a war: you want your answers in one hour rather than one day, and it makes a big difference. A similar example is real-time TV studios, which probably benefit from distributed computing as well. Chess-playing machines and the like also belong to this category. Big data also shows up in this category – when interactively exploring data, you would like queries to run in reasonable time.


Best operating system for a computing degree? Not sure which OS is best to invest in for my computer science degree. Have had varying opinions - from your experience in education or working in the sector, what is the operating system that will treat me the best for the next three years of my degree?

I'm in the final year of a 4-year engineering degree program in Electronics and Communication Engineering. I have installed and use Kubuntu for the past 3 years and I love it!

It is lightweight and crashes very rarely (with 8 GB RAM, but 4 GB RAM is also useable with fewer applications runnning concurrently).
Most updates can be done without restarting your computer and you are not forced to update.
Beautiful and intuitive GUI (KDE)
Free KDE development tools like KDevelop and Kate are awesome!
Easily install and update software using Discover application.
Different modes and a fully customisable desktop
Tons of free software that can be installed.
The PDF reader, Okular is really good!
Learning Unix and Linux administration is a very valuable skill in the computing industry.


Travelling salesman very rough min and max estimates Is there a way to find very rough minimum and maximum estimates for the travelling salesman problem? The estimates only need to be within the roughly same magnitude, but it's important that the minimum estimate is lower (or equal) to the actual distance and that the maximum estimate is higher (or equal) to the actual distance.

EDIT:
Metric TSP unfortunately does not apply.
To add some context: I'm searching for non-dominated fronts (pareto fronts) for a Multiobjective TSP, e.g. optimizing for multiple variables like travel time and distance. I'm using NSGA-II which requires an upper and lower bound for each objective function, which translates into rough estimates for single-objective TSP, with the constraint that the upper estimate has to be higher than the real max distance and vice versa.

It is conjectured (but unproven) that the Held-Karp relaxation (not the Held-Karp algorithm) has an integrality ratio of 4/3 (on metric TSP). Various proofs exists for even better bounds if some assumptions are made.

Practically it performs even better, gaps of ~2% are normal, and there is a lot of literature about adding more cuts that get that gap (typically) a fair way below 1%, but that would not fit with your goal of "fast and easy to implement" anymore. Just the basic degree constraints + lazy sub-tour elimination is, when using an existing LP solver, both fast and easy, and a lot better than taking one of the well known upper bounds and dividing them by their approximation ratio (which tends to be give terrible results, because they typically approximate much better than their worst case, resulting in an overly optimistic lower bound).


What is $C_4$ + two "ears" called? A graph with $C_3$ + 3 "ears" is called a net graph.

In general, $C_n$ + $n$ pendant vertices are called sunlet graphs.

Is there a name for 4-sunlet graph minus two pendant vertices?

According to ISGCI this graph is known as "A".

Looking at some references, it also seems that there is really no common well-known name.


Encoding the pigeonhole principle in CBMC CBMC is a Bounded Model Checker for ANSI-C and C++ programs. It also supports SystemC using Scoot. It allows verifying array bounds (buffer overflows), pointer safety, exceptions and user-specified assertions.

For the pigeon-hole principle I understand that the constraints are:

Each Pigeon is in some Hole.
Two different Pigeon can't be in same hole.

Let's take an example of 4 pigeons and 3 holes. I need to convert this into a CBMC check. I'm trying using two for loops, but I can't find how to do it.

If I understand correctly, you're actually looking for a technique to check if an out-of-bounds condition exists (more pigeons than pigeonholes).

Here's some example code that fits your analogy. I think you're asking about this technique as an analogy to whatever problem you're actually trying to encode, but next time be direct with what problem you want to solve rather than an analogy :)

/* pigeonhole.c */
int main() {
  _Bool holes_occupied[3];
  unsigned int pigeon;
  for (pigeon = 0; pigeon < 4; ++pigeon) {
    holes_occupied[pigeon] = 1;
  }
  return 0;
}

Run with:

cbmc --bounds-check pigeonhole.c

VERIFICATION FAILED (with error trace)


How to prove T Z = Z for binary representation of natural numbers in Coq I have defined an Inductive in Coq for binary representation of natural numbers as follows:

Inductive bin : Type :=
  | Z : bin
  | T : bin -> bin
  | M : bin -> bin.

and two recursive functions to convert between nat and bin types as:

Fixpoint nat_to_bin (n : nat) : bin :=
  match n with
    | O => Z
    | S n' => incr (nat_to_bin n')
  end.

and

Fixpoint bin_to_nat (b : bin) : nat :=
  match b with
    | Z => O
    | M b' => S (mult 2 (bin_to_nat b'))
    | T b' => mult 2 (bin_to_nat b')
  end.

to show that bin_to_nat is the inverse of nat_to_bin I need to prove that T Z = Z by using these tactics that I know: simpl reflexivity destruct rewrite replace induction please recommend some clues showing how to do this. Thank you!

Edit

The incr implementation is

Fixpoint incr (b : bin) : bin :=
  match b with
    | Z => M Z
    | T b' => M b'
    | M b' => T (incr b')
  end.

to show that bin_to_nat is the inverse of nat_to_bin I need to prove that T Z = Z

No, you can't prove that T Z = Z because it is false:

Lemma TZ_neq_Z : T Z <> Z.
Proof.
  discriminate.
Qed.

Indeed, distinct constructors of an inductive type always lead to distinct terms.

That doesn't mean you can't prove that bin_to_nat is the inverse of nat_to_bin though.


Prove that every maximal flow yields the same minimal cut Hi I'm trying to prove the following proposition:

Given a network $G,s,t,\omega$ where $\omega$ is the capacity, create a minimal cut cut  ${S=\left\{ (s,v)\in E_{G_{r\_max}}\right\} }$ where $G_{r\_max}$  is graph representing the the residual network(meaning we take the group of all vertices that are reachable from s in $G_{r\_max}$). So that the cut is $\left(S,V\backslash S\right)$.

Given two maximal flows $f_1\neq f_2$ prove that $\left(S_1,V\backslash S_1\right)=\left(S_2,V\backslash S_2\right)$ (which are defined in the above mentioned form for each maximal flow).

I've tried proving by assuming the contrary and saying that $S_1 $ is not subset of $S_2$.
Tried to say that this leads to $\exists \ v\in S_1 \ \ \mbox{s.t} \ \ v\notin S_2$.
Tried looking at the intersection and union of these groups but to no avail.

I'd appreciate some guidance\explanation as to how best prove this claim.

Here are some hints.  Instead of trying to prove the contrapositive, try proving the statement directly.  If $f_1 \ne f_2$, then that means that there is some edge $e$ where $f_1$ sends a different amount of flow down than $f_2$ does.  What does that imply about the residual graph for $f_1$, vs the residual graph for $f_2$?  Those two residual graphs must differ in some specific way: how?  What does that difference imply for $S_1$ vs $S_2$?  Try writing out some small examples, with small graphs, where you draw the flows, residual graphs, and cuts explicitly.  What do you find?

I suggest you spend a bit more quality time on your own, trying a bit harder to solve it yourself.  This is your exercise; you need to solve it yourself.  And you need to put in a bit more effort to explore this problem.  Don't give up easily -- you can do it!


What is the difference between following two finite automata? I'm solving problem of drawing the finite automata of (1+0)*(10). Which is any string ends with 10. I've drawn the following diagram for this one:

But somewhere in solution it is given the following diagram:

I can't understand what is the difference between these two? Is my solution is correct? If it is not than what changes in my solution will take me to this given solution?

As many have pointed out in the comments, your automata is non-deterministic. There are two paths you could take from q0 when you read a 1. When running a non-deterministic automata, you need to keep track of all possible paths and see if any of them end up in an accepting state. If you don't keep track of all different possible states you could be in, your solution might never accept any string, if it choses the looping 1 all the time, never leaving q0.

Converting a non-deterministic finite automata (NFA) to a deterministic finite automata (DFA) can be done using a simple algorithm. It's quite slow, but for small examples, it's no problem doing it by hand. There are good videos explaining how to do this in slightly different ways.

The main idea is that you build a table of all possible states you could be in.
For your NFA, I'll label the nodes q0, q1 and q2 from left to right, starting at q0.

At q0 we can reach q0 or q1 when reading a 1.
At q0 we can reach q0 when reading a 0.

That's the first step. Now we have multiple states at the same time. We already did q0 so we have the (q0 or q1) state left.

When reading a 1 from (q0 or q1) we can end up in (q0 or q1). q0 can reach (q0 or q1), and q1 cannot reach anywhere.
When reading a 0 from (q0 or q1) we can end up in (q0 or q2). q0 can loop back to itself, and q1 can reach q2.

And lastly, the (q0 or q2) state.

When reading a 0 from (q0 or q2) we can end up in q0. q2 doesn't have any outgoing edges, and q0 can only reach itself.
When reading a 1 from (q0 or q2) we can end up in (q0 or q1). q2 doesn't have any outgoing edges, and q0 can reach (q0 or q2).

Those are all our possible state transitions in the NFA.

Our list of states used in the transitions above are:

q0
(q0 or q1)
(q0 or q2)

The edges are:

q0 + 0 -> q0
q0 + 1 -> (q0 or q1)
(q0 or q1) + 0 -> (q0 or q2)
(q0 or q1) + 1 -> (q0 or q1)
(q0 or q2) + 0 -> q0
(q0 or q2) + 1 -> (q0 or q1)

You can see that this is the bottom graph in your question, with the states renamed.

It's worth noting that in real life regex engines, NFA's are used because this conversion is very expensive for large automata. It's cheaper and safer to keep track of all states instead of doing the conversion. One notable example is the RE2 library. Most other implementations use backtracking, which is O(2^n) for an n-length string. RE2 is exponential in the expression length, but linear in input. Developers write the expressions, attackers write the input.


How to understand the notion of boolean query via Immerman's definition A query is any mapping $I:STRUC[\sigma] \to STRUC[\tau]$ that is polynomially bounded. A boolean query is a map $I_b: STRUC[\sigma] \to \{0,1\}$. A boolean query can also be thought as the susbset:
  $$
\{ A \in STRUC[\sigma] \ \mid \ I_b(A) = 1 \}
$$

From this definition of query, used by Immerman in his book "Descriptive Complexity", how are boolean queries and general queries related? It seems from the definition that they are two different things entirely. Is there an intuitive way to link the two concepts? Thank you!

Boolean queries are a special case of general queries. You can take $\tau$ to be some convenient vocabulary and choose a pair of $\tau$-structures to represent "true" and "false".

FOr a  concrete example, take $\tau$ to be the vocabulary with a single nullary relation symbol $T$. Now, associate "true" with the $\tau$-structure $\mathfrak{T}$ that has $|\mathfrak{T}|=\emptyset$ and $T^\mathfrak{T}=\{\langle\,\rangle\}$ (i.e., the nullary relation that contains the empty tuple) and "false" with the structure $\mathfrak{F}$ that has $|\mathfrak{F}|=\emptyset$ and $T^\mathfrak{F}=\emptyset$ (the nullary relation that doesn't contain the empty tuple).

Empty universes are a bit awkward, since they mean that $(\forall x\,\varphi) \rightarrow \exists x\,\varphi$ isn't a tautology. If you don't like that and/or you don't like nullary relations, make the relation $T$ unary and use a one-element universe.


How to sort an array $A[1..i..n]$ where $A[i] \in \{1,2,..,n^5 \}$ in $\Theta (n)$ time? I need to write a sorting algorithm which will sort an array $A[1..n]$, $1 \le i \le n$ such that $A[i] \in \{1,2,..,n^5 \}$, all numbers are positive integers in $\Theta (n)$ time.

The solution must use some combination of radix/counting/bucket sort and possibly select algorithm, it can't use any advanced concepts or structures.

I thought of the following:

0) Convert the numbers into base $n$.

1) Count how many digits each number of the array $A$ contains. We know that the number with max amount of digits will be $n^5$. It'll have $\lfloor{\log_b n^5} \rfloor +1= \lfloor 5\log_b n \rfloor+1$ digits, where $b$ is the base.Because we changed the base to $n$, there will be $\lfloor 5\log_n n \rfloor+1 =6$ unique digit lengths. Create an array countArray which will contain how many occurrences of tens, hundreds etc are.

2) Create subArrays which will contain numbers of the same amount of digits and run radix sort on each such subarray. Radix-Sort runs in $\Theta(d(n+b))$ in general and in our case it will become $\Theta(6(n+n)=\Theta(6n)=\Theta(n)$.

3) In the last step we copy the sorted subarrays into the output array.

Below is the pseudocode but I'm interested if my idea is correct and if the time complexity of my algorithm is $\Theta(n)$:

1 MySort(A, n)                    //A is the array, n is array length
2    uniqueDigitsNum <- 5log_n(n) + 1=6
3    init countArray             // the array of length uniqueDigitsNum
4    for i <- 0 to n             //O(n)
5        //B is a helper array which will store how many digits are in a given number
6        countDigits(A[i], B[i])
7        countArray[B[i]]++      //update the count of how many times we see x digits in CountArray
8    // init a 2d array which will contain uniqueDigitsNum subarrays
9    init subArrays of length uniqueDigitsNum
10    for k <- 0 to uniqueDigitsNum  //O(6)
11        init subArrays[k] of length countArray[k]
12    for k <- 0 to uniqueDigitsNum  //O(6n)
13        Radix-Sort(subArrays[k])   //O(countArray[k])
14    //we'll need 'j' to know at which index to start copying the next subarray in the big output array
15    j <- 0
16    for k <- 0 to uniqueDigitsNum  //O(n)
17        for j to countArray[j]     //O(countArray[j])
18            outputArray[j] <- subArrays[k][j]

Radix sort for integers of arbitrary length has $\mathcal{O}(mn)$ time complexity, where m is the length of number.
Count digits takes $\mathcal{O}(\log(n))$ time, so, your cycle will take at least (in worst case though) $\mathcal{O}(n \log(n))$ time which is the best possible for general case of sorting problem. Because to find complexity of 2-level cycle, you need to find complexity of subcycle and multiply them.

Of course, there exists an algorithm that can sort any array of numbers in $\mathcal{O}(n \log(n))$ time and $O(\log(n))$ space.


P decision problem that potentially requires at least $\Omega(n \log n)$ in the Turing model? Currently, it is not proven that $NP \geq O(n \log n)$ in the Turing Machine Model.

The weakness of this statement can be illustrated by NP-complete problems, which we think require way more time. But I'm looking for the easiest-to-solve decision problem in P that probably has $\Omega (n \log n)$ as lower bound in the Turing machine model (I say "probably", because proving it would be a scientific breakthrough). Such a problem would best illustrate the power of the statement "$NP \geq O(n \log n)$".

It inspired me to ask about a candidate: Deterministic linear time algorithm to check if one array is a sorted version of the other, but it may not be the simplest because Yuval pointed out it probably requires more than $O(n \log n)$ in the Turing machine model.

We know that there exists some problem in $P$ that can't be solved in $O(n \log n)$ time on a Turing machine; this follows from the time hierarchy theorem.  As a result, there definitely exists some problem in $NP$ that can't be solved in $O(n \log n)$ time on a Turing machine.  So your "it is not proven that..." statement is wrong; that is proven.

Model of Computation

When dealing with relatively "small" running times, like $O(n \log n)$, the model of computation can make a big difference.  For instance, there might be problems that are solvable in $O(n \log n)$ time on a multitape Turing machine but not on a single-tape Turing machine.  Also, some researchers have studied problems that can be solved by circuits.

For circuits, the situation is rather depressing.  We cannot identify any computable function $f:\{0,1\}^n \to \{0,1\}$ where we have a lower bound on circuit complexity that is $\omega(n)$.  We know there exist problems that can't be solved by any circuit of size $O(n)$, but we can't identify any specific problem where we can prove this is the case.  See, e.g., https://cstheory.stackexchange.com/q/21400/5038.  This illustrates just how hard it is to prove lower bounds (see, e.g.,
https://cstheory.stackexchange.com/q/17789/5038 and references therein).

Plausible candidates

Nonetheless, there are many plausible candidates where it might not be possible to solve them in $O(n \log n)$ time.  For instance, 3SUM and other similar problems don't appear to have any $O(n \log n)$-time algorithm that we can find, so they might be reasonable candidates.  Other examples include all-pairs shortest paths and linear programming.

For more, see https://cstheory.stackexchange.com/q/1284/5038 and https://cstheory.stackexchange.com/q/17578/5038.

Careful with those Omegas!

You wrote that you wanted to find a problem that can't be solved in $O(n \log n)$ time.  You also wrote that you wanted to find a problem that takes $\Omega(n \log n)$ time to solve.  Beware that those aren't the same thing.  The former is equivalent to looking for a problem that takes $\omega(n \log n)$ time to solve.

It is known that any language (decision problem) that can be solved in $o(n \log n)$ time on a single-tape Turing machine is in fact a regular language.  Thus if you take any language that is not regular but is in $P$, it follows that the running time for a Turing machine to decide it is $\Omega(n \log n)$.  Beware that this might not be what you want: this means the running time might be $\Theta(n \log n)$ or it might be even larger.  I suspect you meant to ask for a problem that cannot be solved in $O(n \log n)$ time, i.e., that requires $\omega(n \log n)$ time.


Name of an Exact Cover by 3 sets variant Exact cover by 3-sets is $\sf{NP}$-complete:

Instance: Given a finite set $X = \{ x_1,x_2,...,x_{3n}\}$ of $3n$ elements and a collection $C = \{ ( x_{i_1}, x_{i_2}, x_{i_3}) \}  $ of $m$ 3-elements subsets of $X$;
Question: Find a subcollection $C'$ of $C$ such that every element in $X$ is contained in exactly one member of $C'$.

The problem remains NPC even if we add the following condition:

every element of $X$ appears exactly in three subsets of $C$

Has this variant an "official" name?

Gonzalez called this variant RXC3, for "Restricted Exact Cover by Three Sets."


For two sets of points find if second one is result of linear transformation of the first Say we have two sets of points in vector-2 space (In actuality need to solve this problem in vector-3 space but decided to start with a simpler problem). The points in the second set are the result of transformation of the points in the first set. It's not known which point in the first set corresponds to which point in the second set. What needs to be calculated is if the points of the second set can be seen as the linear transformation of the first set. So basically finding whether there exists a 2 by 2 matrix, which if applied to the first set gives the second set. And if so calculating it.
Should a problem like this be solved using computational geometry, like sweep line algorithm to compare all points between sets?

In 2D, a linear transformation has the form $v \mapsto Mv$ where $M$ is a $2\times 2$ matrix, so the transformation has four parameters.  Thus, the transformation is uniquely determined if you have two points $p_1,p_2$ from the first set and two points $q_1,q_2$ and if you know that $p_1$ transforms to $q_1$ and $p_2$ to $q_2$.  You can find this linear transformation explicitly by solving a system of linear equations.
Consequently, the following algorithms works:

Pick two points $p_1,p_2$ arbitrarily from the first set.
For each possible way to pick two points $q_1,q_2$ from the second set:

Find the unique linear transformation $T$ that maps $p_1$ to $q_1$ and $p_2$ to $q_2$.
Check whether applying $T$ to the first set gives you exactly the second set.  If so, output $T$ and halt.

If you reach this point, output that no such linear transformation exists and halt.

This algorithm is guaranteed to be correct: it will find the linear transformation, if any exists, because we have tried all possible pair of points that $p_1,p_2$ could match with.
The worst-case running time is $O(n^3)$, if $n$ is the number of points in each set.  That's because you loop over ${n \choose 2} = O(n^2)$ pairs of points in step 2.  Each iteration of the loop involves solving a system of four linear equations (takes $O(1)$ time) and checking whether it is a valid solution (could take $O(n)$ time in the worst case, since you might have to apply $T$ to each point in the first set).
However, heuristically, I expect the running time will typically be $O(n^2)$.  That's because typically you can reject most candidate transformations $T$ immediately: if you apply $T$ to one point in the first set, and get a result that is not in the second set, you can reject $T$ without applying it to any other points in the first set.  Thus, heuristically, I expect that typically each iteration of the loop will usually complete in $O(1)$ time.  That said, there do exist arrangements of the points where this is not correct.
The generalization of this algorithm is RANSAC, which can handle the situation where most points of the first set can be matched to the second set but some cannot.


Number of Pairs in Array so hey, I've been recently reading about the Two-Pointer algorithm that allows us to find pairs $(i,j)$ such that $a[i] + a[j] = x$ in $O(m+n)$ instead of the trivial $O(mn)$ time.

I was wondering how can I find the number of pairs $(i,j)$ in time less than $O(mn)$.  I was trying to use Two-Pointer but it seems that it doesn't work when there duplicate elements because there can be no way of moving one pointer without missing some pairs like $[1, 1, 2, 3, 3]$ and $x = 4$ or maintaining the linear time, unless I'm missing something here.

  Is there is some magical way of finding the number of pairs $(i,j)$ such that $a[i] + a[j] = x$ in less than $O(mn)$ time?

You observed correctly that the number of pairs can grow quadratically with input size. In the worst case, the array contains only two types of numbers, but with great multiplicity.

$$[1,1,1,1,1,2,2,2,2,2]$$

Here, each of the five ones can be combined with each of the five twos, thus creating 25 pairs that sum up to three. It is generally impossible to visit each pair once and maintain linear time complexity.

Luckily, it is not neccessary to visit each pair once, as we can calculate the multiplicity of the pair from the multiplicities of its members. In this case:

$$5 \cdot 5 = 25$$

To find all pairs in linear time, run-length encode the array first. So

$$[0,1,1,1,1,1,2,2,2,2,2,3]$$

becomes

$$[(0,1),(1,5),(2,5),(3,1)]$$

Then, apply the two-pointer algorithm and calculate the multiplicity of each resulting pair directly. Here, the result could be a pair of zero and three with multiplicity one, and a pair of one and two with multiplicity 25.

$$[(0,3,1),(1,2,25)]$$

In total, there are 26 pairs.


Why is Two-Phase Commit (2PC) blocking? Can anyone let me know, why 2PC is blocking when the coordinator fails? Is it because the cohorts don't employ timeout concept in 2PC?

Good reference: Analysis and Verification of Two-Phase Commit & Three-Phase Commit Protocols, by Muhammad Atif,

Elaboration of the question:

Let’s say, a coordinator sends 1st message (PREPARE-COMMIT). At this point assuming all cohorts are reachable, there are two possible outcomes- either all cohorts reply YES or at least one cohort replies NO. In either way, let’s assume the coordinator crashes before it can send the 2nd message (COMMIT/ABORT).
Since 2PC uses only 2 messages, in order to keep the cohorts consistent, the cohorts can never apply a commit without explicitly receiving a COMMIT message. So, when a coordinator crashes, the cohorts can either (1) apply a ABORT using a timeout or (2) can remain in waiting state indefinitely. It is hard to believe that a 2PC would employ option (2) i.e. waiting indefinitely. Therefore, if option (1) is chosen, then why do we tag 2PC as blocking when a coordinator dies?

Is it because the cohorts don't employ timeout concept in 2PC?

Yes, in one case they can not use a timeout. It is described in the paper too (II.B.1):

  The Two-Phase Commit Protocol goes to a
  blocking state by the failure of the coordinator when the
  participants are in uncertain state. The participants keep
  locks on resources until they receive the next message
  from the coordinator after its recovery

In practice that 'uncertain state' means voting 'yes'. After a cohort votes 'yes', there is no going back, it waits for the global decision. (Other cases are fine: by voting 'no', the given cohort immediately knows that the global decision is also a 'no', and if the coordinator dies even before initiating the voting round, cohorts may decide voting 'no' based on a timeout)