How can you check if a 2SAT problem has a bad loop im trying to figure out why this is true

The clauses {a,b}, {b,~c}, {c,~a} constitute a 2SAT problem with an implication graph without bad loops.

Can someone show me how to illustrate this and indicate how i can find wether any 2SAT problem has a bad loop or not, Thank you so much :)

The implication graph is constructed using the following ingredients:

Vertices: One vertex for each variable, and one for each negation of a variable
Edges: For each clause {x,y}, create an edge from -x to y and one edge from -y to x

The following should be the implication graph corresponding to your set of clauses:

A bad loop (I'm guessing this is what you want, haven't encountered that wording before) is a loop in the implication graph that contains both a variable and its negation (i.e. both x and -x). Clearly there is no such loop in your case.

Why "bad loop"? It is because each edge represents an implication that necessarily must hold for your 2-SAT instance. For example, the first clause reads "a or b". If this clause is to be satisfied, then we must have one of the two variables true. So:

If a isn't true (i.e. -a is true), then b must be true, which is the implication -a$\to$b
If b isn't true (i.e. -b is true), then a must be true, which is the implication -b$\to$a

In a "bad cycle", you have a cycle of such implications, so that x$\to$...$\to$-x$\to$...$\to$x. Such a cycle of implications can never be satisfied, otherwise x would be both true and false at the same time. So if you have any bad cycles, the 2-SAT formula is unsatisfiable!

In fact, a 2-SAT formula is unsatisfiable when, and only when, there is a bad cycle in the implication graph. So your formula is, by the absence of bad loops, satisfiable. The proof of satisfiability in the case of no bad loops even yields a poly-time algorithm to find a satisfying assignment (which is great : ) )

So how to assign values to the variables and satisfy your (or any) 2-SAT formula? I'll refer to https://en.wikipedia.org/wiki/2-satisfiability#Strongly_connected_components for the algorithm, but be warned that you need to know of the concept of "strongly connected component" to fully understand the algorithm.


How does the kleene star and union work in a context free grammar? Im in a functional languages computer science class and I have a question on the use of the kleene star and the Union in a context free grammar.

for the kleene star I have an idea of how I might do it.
    for example

 {0^n 1^n | n in the set of natural numbers}

I think it would look something like this.

 S-> 0S1 | A
 A-> S | lambda

where lambda would mark closing or ending the string. Is this right?

as for how the union would I dont understand at all how it would work. wer were given an example that looks like this

 {0^n1^n | n in the set of natural nubmer} U
 {0^n1^2n | n in the set of natural numbers}

I know how I would make a context free grammar for either of these alone but I dont know how the union comes into play with this.

This is how you can implement star and union operations over context-free languages given their grammars.

Given a grammar $G$ for the language $L$, we can take a new non-terminal symbol $T$ not appearing in $G$, and add the following production:

$$ T \rightarrow TS \;|\; \epsilon$$

where $S$ is the start symbol of $G$. $T$ is now a new start symbol. The language of the resulting grammar is $L^{*}$.

Similarly, given grammars $G_1$ and $G_2$ for languages $L_1$ and $L_2$, respectively, we can take a new non-terminal symbol $T$ not appearing in $G_1$ nor in $G_2$, and add the following production:

$$T \rightarrow S_1 \;| \;S_2 $$

where $S_1$ and $S_2$ are the starting symbols of $G_1$ and $G_2$, respectively. $T$ is now a new start symbol. The language of the resulting grammar is $L_1 \cup L_2$. Also, make sure that you use different non-terminal symbols in $G_1$ ad $G_2$.


String inputs in Machine Learning Several popular machine learning algorithms such as Logistic regression or Neural networks require its inputs to be numeric.

What I'm interested in is how you make these algorithms work on non-numeric inputs (such as short strings).

As an example, let's say we're building an email classification system (spam/not spam), where one of the input features is the sender address.

To be able to use a learning algorithm, we need to represent the sender address as a number. One way is to simply number the senders 1..n. Our training set might then look like this:

This won't work, however, because algorithms such as Logistic regression or Neural networks learn patterns in the input data, while in our example, the output looks totally random to the algorithm. Indeed, once in a university class, we tried to train a Neural network on a dataset that looked like this and the network was unable to learn anything (the learning curve was flat).

Would you use Logistic regression or Neural networks in this example at all? If yes, in which way? If not, what would be a good way to classify emails based on sender address?

A perfect answer would discuss the email classification example as well as handling short strings in ML in general.

One of the popular models is the Bag of Words model

Also, you can model the words as integers.. they have 'relative distance metrics' for that, and capture the very essence of the classification process. However a downside to that is the preprocessing step is expensive and also you need to have some domain knowledge.

A pretty famous distance metric is the Levenshtein distance which is based on the the number of single character edits. eg. that is, $d(walk,talk)<d(walk,plod)$.

The metrics depend upon the context of the classification process.. for example your distance metric for classifying rhyming words will be different from those designed to classify synonyms/words conveying similar meanings.For a list of string metrics, take a look at this wikipedia article.

Also, you can take a look at this review paper.


Given the set of length of triangle, find the Maximum Area Triangle Suppose we are given an array of numbers representing lengths of line segments.  Find which three of these segments can be assembled into a triangle with maximum area.

I can compute the areas of all $O(n^3)$ possible triangles in $O(n^3)$ time using Heron's formula, and then return the largest. Can this be improved to $O(n^2)$ time? Or even faster?

There is an $O(n^2)$ algorithm. By Heron's formula, the area of a triangle whose sides have length $a$, $b$, and $c$ is $S = \frac{1}{4}\sqrt{4a^2b^2 - (a^2+b^2-c^2)^2}$. Thus if we fix $a$ and $b$, the area is maximized when $c$ is closest to $\sqrt{a^2+b^2}$. A simple approach is to try all $O(n^2)$ possible pairs of $a$ and $b$ and perform binary search for the best value of $c$. This approach yields an $O(n^2 \log n)$ algorithm.

To achieve $O(n^2)$, we first sort the lengths of line segments ($l_1, l_2,\ldots, l_n$) in non-decreasing order. Let $a = l_i$ and $b = l_j$ with $i < j$, and let $k$ be the position in which $l_k$ is closest to $\sqrt{l_i^2 + l_j^2}$. When $j$ runs from $i+1$ to $n$, $k$ also increases gradually to $n$. Thus finding $k$ has an $O(1)$ amortized run time, i.e., the whole algorithm takes $O(n^2)$.

Update 11/26/2013:

An easier $O(n \log n)$ algorithm is to sort $l_i$ in a non-decreasing order, and find  $3\leq k \leq n$ that maximizes the area of the triangle assembled from $l_{k-2}, l_{k-1}$, and $l_{k}$. It follows from the fact that if $i ,j < k$ then $S(l_i, l_j, l_k) \leq S(l_{k-2}, l_{k-1}, l_k)$ (can be proved by taking the derivative of $S$ and that $l_k$ is the length of the longest side).


Number of grid points in d-dimensional sphere of radius r Given integers $d$ and $l$, compute the number of grid points $x \in N^d$ that satisfy $\sum_i x_i^2 \leq l$ (i.e. $||x||_2^2 \leq l$). (Think of $l$ as $r^2$).

The problem is obviously in #P. Is it in P or a smaller class? What if in place of $l_2$ we use $l_p$?

I'll assume $l,d$ are given in unary, otherwise the problem has a trivial exponential lower bound as the number of solutions can be $\Omega(2^d)$, e.g. in the case of $l=d$, each entry could be zero or one.

If we are given $1^l,1^d$, then this can be solved in polynomial time. Suppose $d=2^k$ (this will simplify things), and let $A(d,l)$ be the recursive algorithm for counting the number of solutions which is defined as follows:

$A(d,l)=\sum\limits_{l'=0}^l A\left(\frac{d}{2},l'\right)A\left(\frac{d}{2},l-l'\right)$

I'm pretty sure $A$ can be made to run in polynomial time using memoization, by keeping a $d\times l$ size table of the values we computed so far.


In reference to the Chomsky hierarchy (and automatas), Which is the linear feedback shift register Languages/automaton? The Chomsky hierarchy is a guideline on language expressive power. The linear feedback shift register is a very interesting "element" to structure a language and there is a large theoretical literature.

In reference to the Chomsky hierarchy (and automata), which is the linear feedback shift register languages/automaton ?

It has a finite memory, so it's just a DFA (or some of the output-producing variants). If you allow a growing/shrinking feedback register, it is probably equivalent to a Turing machine.


Lock-free, constant update-time concurrent tree data-structures? I've been reading a bit of the literature lately, and have found some rather interesting data-structures.

I have researched various different methods of getting update times down to $\mathcal{O}(1)$ worst-case update time [1-7].

Recently I begun looking into lock-free data-structures, to support efficient concurrent access.

Have any of these worst-case $\mathcal{O}(1)$ update-time techniques been used in the implementation of lock-free data structures?

I ask because; to me, they seem like the obvious practical extension of this "theoretical enhancement".

Tarjan, Robert Endre. “Updating a Balanced Search Tree in O(1) Rotations.” Information Processing Letters 16, no. 5 (1983): 253 – 257.
Driscoll, J R, N Sarnak, D D Sleator, and R E Tarjan. “Making Data Structures Persistent.” In Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, 109–121. STOC  ’86. New York, NY, USA: ACM, 1986.
Levcopoulos, C., and Mark H. Overmars. “A Balanced Search Tree with O(1) Worst Case Update Time.” Acta Inf. 26, no. 3 (November 1988): 269–277.
Fleischer, Rudolf. A Simple Balanced Search Tree With O(1) Worst-Case Update Time
Dietz, Paul F, and Rajeev Raman. “A Constant Update Time Finger Search Tree.” Information Processing Letters 52, no. 3 (1994): 147 – 154.
Lagogiannis, George, Christos Makris, Yannis Panagis, Spyros Sioutas, and Kostas Tsichlas. “New Dynamic Balanced Search Trees with Worst-case Constant Update Time.” J. Autom. Lang. Comb. 8, no. 4 (July 2003): 607–632.
Brodal, Gerth Stølting, George Lagogiannis, Christos Makris, Athanasios Tsakalidis, and Kostas Tsichlas. “Optimal Finger Search Trees in the Pointer Machine.” J. Comput. Syst. Sci. 67, no. 2 (September 2003): 381–418.

$O(1)$ doesn't help in and of itself.  In a lock-free data structure there needs to be a single atomic instance when your data structure appears to change.  All the representation invariants need to be in force both immediately before and immediately after that atomic instant.

This means that if you are doing a modification to the data structure the important characteristic is that you can do all the mods on a private data structure and then swap in the modifications in a single atomic instruction.

Lock-freedom is usually easiest when your data structures are immutable (purely functional).  You simply keep a global pointer to the current version of the data structure.  Readers don't need to lock anything.  Modifications to the data-structure are effected by swapping the global pointer to one immutable data structure to another.

For example: if you have a purely functional tree balanced tree you:

Record the current global pointer to the root of the tree.
Create a new tree that inserts or deletes a node.  (This is logarithmic in time and space in the number of nodes currently in the tree, and involves creating new nodes from the modification point up to the root, and just pointing everything new at the old parts of the previous version of the data structure.)
Atomically compare and swap the global pointer to the root.  (Note that this might fail if another modification has happened between the time you recorded the old root pointer and now.  If this happens you go back to step 1 and try again.  This is so-called "optimistic concurrency control.")

Note that the most important part is what I said above about needing to maintain representation invariants.  It is usually not sufficient to have an algorithm that atomically makes a change in the middle of the tree.  Why?  For example: you might have a reader thread that is in the process of doing a preorder traversal of the tree.  If you modify a node that is an ancestor of the node they are currently reading then you are going to invalidate preconditions that they thought they had enforced.  The reader needs to be able to work with the data structure exactly as it was before you made your change, or exactly as it will be after you've made your change.  Not something in between.

Edit: As @Raphael pointed out there are techniques for making mutable data structures lock-free.  A proof by construction that this can always be done is: As long as you have a single global pointer to the "top" of your data structure, even if it is mutable you can always copy the entire data structure, make your mods to the copy, and then, using optimistic concurrency control, try to compare-and-swap the pointer to your newly minted data structure in for the original.  The beauty of functional tree-based data structures is that they keep the cost of copying down at $O(log(N))$ of a size $O(N)$ data structure.


Relativized world where $LogCFL^A=PSPACE^A$ I wonder whether there is a known relativization barrier against proving $LogCFL\neq PSPACE$. Hence I'm looking for a language $A$ for which $LogCFL^A=PSPACE^A$.

One could try $A:=TQBF$, where $TQBF$ is the $PSPACE$-complete problem to decide true quantified Boolean formulas. But relativising space-bounded classes is a very tricky business, as Emil Jeřábek tried to explain to me.

Maybe it is easier to look at the problem from the other side: Both $NL\neq PSPACE$ and $CFL\neq PSPACE$ are known. I heard multiple times that one "usually considers LOGCFL instead of CFL, since it has nicer closure properties". So maybe $LogCFL\neq PSPACE$ is known. I noticed that the German wikipedia article on NP claims that $LogCFL\neq PSPACE$ would be known, but I couldn't verify this. But if this should be known indeed, then I wonder whether it also applies to $AC^1$, or whether $LogCFL$ is really the current limit where separation from $PSPACE$ can still be proven.

Maybe it is easier to look at the problem from the other side: ... the German wikipedia article on NP claims that $LogCFL\neq PSPACE$ would be known, ...

It is know: $CFL \subset DSPACE(O(\log^2 n))$ was shown in [ 1 ] and "generalized" in [ 2 ] (whatever that means, I don't have full text access to those articles). This algorithm takes superpolynomial time, i.e. it is different from the CYK algorithm taught in Hopcroft and Ullman (and not even mentioned there, despite contrary claims). It directly follows that $LogCFL\subset DSPACE(O(\log^2 n))$ and hence $LogCFL \neq PSPACE$.

  But if this should be known indeed, then I wonder whether it also applies to $AC^1$, ...

The English wikipedia article on complexity classes claims that $NC\neq PSPACE$ would be known. Since $AC^1\subset NC$, this would mean that it also applies to $AC^1$. This separation can be deduced from $NC^k\subset DSPACE(O(\log^k n))$, see for example Lemma 5.4 A circuit of depth $D$ can be simulated in $O(D)$ space or slides 25-28 of this ppt. So it is well known indeed.

  But does this resolve the initial question whether there is a relativization barrier?

Who cares!

1
Lewis, P.M. II, R. E. Stearns, and J. Hartmanis. "Memory Bounds for the Recognition of Context-Free and Context Sensitive Languages." IEEE Conference Record on 1965 Symposium on Switching Circuit Theory and Logical Design.

2
Stephen A. Cook, Path systems and language recognition, Proceedings of the second annual ACM symposium on Theory of computing, p.70-72, May 04-06, 1970, Northampton, Massachusetts, United States


Show that graph is planar or not? Show that the following graph is planar or not.

My first assumption is that this graph is not planar, but could not find a reasonable prove (except saying that I tried drawing it in different ways in plane, but couldn't).

We know that a graph is non-planar if it contains either K5 or K3,3 as minors. I tried getting I subdivision of this graph (by contracting some edges), but failed to get a K5 (which I think should be possible).

Any ideas anyone?

Contract edges $(C,D)$ and $(G,H)$ - and you'll get $K_{3,3}$.


Shortest path in a maze where you can break one wall How would I solve the following problem?

You have maps of parts of the space station, each starting at a prison exit
and ending at the door to an escape pod. The map is represented as a
matrix of 0s and 1s, where 0s are passable space and 1s are impassable
walls. The door out of the prison is at the top left (0, 0) and the door into
an escape pod is at the bottom right (w−1, h−1).
Write a function that generates the length of a shortest path from the
prison door to the escape pod, where you are allowed to remove one wall
as part of your remodeling plans.

I know that without destroying the walls this could be easily solved with the use of Dijkstra. But how to take into account the fact I can destroy one wall?

The only solution I could come up with was to remember two distances for each node: one distance is the "real" shortest path, the second one is the shortest past when I break one (any) wall.

At first I would count all the "real" shortest paths with classic Dijkstra. In the second run I would use Dijkstra again to compute the second parameter of each node: shortest path with exactly one wall broken.

In each iteration the closest node to be chosen (I need to check even vertices that are "one wall away") in Dijkstra is the one with the shortest "real" path or path with a broken wall (whichever is smaller). In case the vertex is one wall away, I only check the "real" path property of course.

This seems correct to me. But is there a better (more efficient) solution?

You can use any search algorithm (including A*) with a tiny alteration from the standard one.

In each node you store whether the path from the start has a broken wall or not. Then when generating the neighbours you can move into a wall only if that flag is false and the neighbours that move into a wall get it set to true.

When Comparing Nodes for equality (for replacing in the heap and or the closed set) that flag counts alongside the position.


Does the Halting Problem prove that true Artificial Intelligence is impossible? The Halting Problem demonstrates that there are things that a machine can never be programmed to do.

Is this proof that true Artificial Intelligence - that is, the ability for a machine to think and reason like humans - is not possible?

If we cannot determine from program description whether it halts we also cannot write algorithm to do so (otherwise we could have determined it from description).
The ability to think and reason like humans is not connected to the halting problem, and the separate problem here is that we do not fully know how people think, so we cannot copy this idea, we are prone to emotions and logic just fails. If you want to create "true Artificial Intelligence" you would have to unlock any restrictions, constraints, let it evolve and think differently otherwise your AI is at the best case clone of you and it will not be self-concious or thinking just ultra advanced processing unit.

If tou like to think about the true AI - human limits are not applicable because if we proved something cannot be done - it is not doable under any circumstances, but if we do not know how to do something (yet) - there is no constraint neither for human nor for the true AI.


Is Huffman Encoding always optimal? The requirement of the encoding to be prefix free results in large trees due to the tree having to be complete. Is there a threshold where fixed-length non-encoded storage of data would be more efficient than encoding the data?

Yes, it is always optimal.

No, there is no threshold where it would use less space to use fixed length non-encoded data.

I found a number of proofs on the Web, but there is sufficient discussion in the Wikipedia article Huffman coding.

This also covers other techniques which achieve higher compression (working outside the space for which the Huffman code is optimal).


Minimum cost flow and Ford-Fulkerson I have a question concerning the use of the Ford-Fulkerson algorithm. Since a minimum cost flow problem is a linear programming problem, it has a dual problem. That dual would be to maximize a certain function. Considering this, is it possible to apply the Ford-Fulkerson algorithm to that dual in order to solve the minimum cost flow problem?

No.  Ford-Fulkerson cannot be used to solve arbitrary linear programming instances.  It can only solve instances that are in the form of "max flow in this flow graph".  The dual doesn't have that form.
The dual is to find the minimum cut.  A standard way to find the minimum cut is by finding the max flow, and then using the max-flow min-cut theorem.


Differences and relationships between randomized and nondeterministic algorithms? What differences and relationships are between randomized algorithms and nondeterministic algorithms?

From Wikipedia

  A randomized algorithm is an algorithm which employs a degree of
  randomness as part of its logic. The algorithm typically uses
  uniformly random bits as an auxiliary input to guide its behavior, in
  the hope of achieving good performance in the "average case" over all
  possible choices of random bits. Formally, the algorithm's performance
  will be a random variable determined by the random bits; thus either
  the running time, or the output (or both) are random variables.

  A nondeterministic algorithm is an algorithm that can exhibit
  different behaviors on different runs, as opposed to a deterministic
  algorithm. There are several ways an algorithm may behave differently
  from run to run. A concurrent algorithm can perform differently on
  different runs due to a race condition. A probabilistic algorithm's
  behaviors depends on a random number generator. An algorithm that
  solves a problem in nondeterministic polynomial time can run in
  polynomial time or exponential time depending on the choices it makes
  during execution.

Are randomized algorithms and probabilistic algorithms the same concept?

If yes, are randomized algorithms just a kind of nondeterministic algorithms?

Non-deterministic algorithms are very different from probabilistic algorithms.

Probabilistic algorithms are ones using coin tosses, and working "most of the time". As an example, randomized variants of quicksort work in time $\Theta(n\log n)$ in expectation (and with high probability), but if you're unlucky, could take as much as $\Theta(n^2)$. Probabilistic algorithms are practical, and are used for example by your computer when generating RSA keys (to test that the two factors of your secret key are prime). Probabilistic algorithm which don't use any coin tosses are sometimes called "deterministic".

Non-deterministic algorithms are ones which "need a hint" but are always correct: they cannot be fooled by being given the wrong hint. As an example, here is a non-deterministic algorithm that factors an integer $n$: guess a factorization of $n$, and verify that all the factors are prime (there is a "fast-in-theory" deterministic algorithm for doing that). This algorithm is very fast, and rejects false hints. Most people think that randomized algorithms can't factor integers that quickly. Clearly this model of computation isn't realistic.

Why do we care about non-deterministic algorithms? There is a class of problems, known as NP, which consists of decision problems which have efficient non-deterministic algorithms. Most people think that the hardest problems in that class, the so-called NP-complete problems, do not have efficient deterministic (or even randomized) algorithms; this is known as the P vs NP question. Since many natural problems are NP-complete, it is interesting to know whether in fact they are not solvable efficiently, in the worst case (oftentimes, the instances which arise in practice are in fact solvable in reasonable time).


Finding a string with some specified hamming distances from other strings I'm searching the space of length $n$ strings (a-z lowercase), which I suppose we could represent as a large graph of strings and hamming distances between the strings.

I'm given some pairs of strings and distances $v_i, d_i$ . I need to find a string which has distance $d_i$ from each each string $v_i$ .

Does there exist an efficient algorithm for finding this? Perhaps it's possible to triangulate to the right string?

Your problem is likely hard. I will consider a decision version of your problem in which the goal is to ask whether there exists any solution. I will show that the binary variant is NP-complete, and the same ideas probably imply that this decision version of your problem is also NP-complete.

Other decision versions of your problem are likely also hard, though perhaps not NP-hard. For example, consider the problem in which you are promised that a unique solution exists, and your goal is to determine the value of its first bit. This problem cannot be NP-hard since it has the same complexity as its complement. Nevertheless, it is probably hard in some other, appropriate sense.

The decision version of your problem that I will analyze asks whether there is an answer.
The problem is clearly in NP, and we prove that it is NP-hard by reduction from X3SAT, a variant of 3SAT in which a formula is satisfiable if every clause contains exactly one satisfied literal. Given a 3CNF on $n$ variables $x_1,\ldots,x_n$, we will consider strings of length $2n$ which encode a truth assignment: a 1 in position $2(i-1)+1$ encodes that $x_i$ is true, and a 1 in position $2(i-1)+2$ encodes that $x_i$ is false.

In order to force that any solution must have exactly one 1 in each of the positions $2(i-1)+1,2(i-1)+2$, we ask that it have distance $n$ from the strings $(00)^n$ and $(00)^{i-1}(11)(00)^{n-i}$ for $1 \leq i \leq n$. In order to force any solution to satisfy all clauses, for every clause we take the string which has 1s in the positions corresponding to the literals in the clause, and we ask that the solution be at distance $(n-3)+2$ from this string. A string satisfies these $n+m+1$ constraints (where $m$ is the number of clauses) if and only if it is a satisfying assignment to the given 3CNF.


Complement of equality problem of Turing machine is recognisable or not Complement of equality problem of Turing machines is unrecognisable or not-recognizable but How?. As per my knowledge it is recognisable if you can decide its accept condition but not Reject and opposite is the case with Unrecognisable. But in complement-Eq problem of TM if a string/input accepted by one but not by other you can Accept it, and reject condition will be undecideable so it should be Turin-recognisable

Let's start with the definition of recognizable:

A language $L$ is recognizable if there exists a Turing machine $T$ such that if $x \in L$ then $T$ halts on $x$, and if $x \notin L$ then $T$ does not halt on $x$.

You haven't specified what you mean by "complement of equality problem of Turing machines", so let me assume that you mean the language $L$ consisting of pairs $(T_1,T_2)$ of Turing machines which do not recognize the same language, that is, there exists $x$ such that $T_1$ halts on $x$ and $T_2$ doesn't, or vice versa.
You could try recognizing $L$ by going over all words $x$, and for which one, checking whether $T_1$ halts on $x$ and $T_2$ doesn't, or vice versa. While you can recognize that $T_1$ halts on $x$, you cannot recognize that $T_2$ doesn't halt on $x$, so this strategy fails.
To show that this language is unrecognizable, you can use a reduction from the non-halting problem. Suppose that $T$ is a Turing machine, and we want to determine whether it doesn't halt on the empty input. Construct a new Turing machine $T_1$ which erases its input and transfers control to $T$, and let $T_2$ be a fixed Turing machine which immediately halts. Then $(T_1,T_2) \in L$ iff $T$ does not halt on the empty input.


Longest Palindrome Brute Force I'm confused by the running time of the following algorithm. I've been told it's $O(n^3)$, but there are only two loops. How can that be?

for(int i = 0; i < s.length(); ++i) {
    for(int j = i; j <= s.length(); ++j) {
        String sub = s.substring(i, j);
            if(isPalindrome(sub) && sub.length() > maxCount) {
                maxCount = sub.length();
                longestP = sub;
            }
    }
}

There's a loop hidden inside isPalindrome(). Possibly also one inside substring() and/or length(), depending on how they're implemented.

You can't just count loops. When we say that an algorithm runs in time $O(n^3)$, we mean that it takes "at most roughly" $n^3$ basic steps. You need to check whether the steps of the algorithm really are basic, or whether they also involve iterations through data structures.  "Basic" corresponds to something like "taking a fixed number of machine instructions, regardless of the input" but this is an informal analysis, so I'm not going to try to give a formal definition.

There's also the technicality that any algorithm that runs in, say, exactly $n^2$ steps runs in time $O(n^3)$, time $O(n^4)$, time $O(2^{2^n})$ and so on, since the definition of $O(\cdot)$ involves an "at most".


What are applications of Coin Change problem? I've read so many about the Coin Change problem, debates about wheather it is solvable using Greedy, Dynamic Programming and so on.

Nevertheless I cannot find an application of this problem.

What are applications of Coin Change problem?

This is going to sound very silly but, I once had to implement the coin change solution for the purpose of... distributing change!

The application was a soda pop vending machine that could accept bills and coins and dispense coins.

The spec required the use of a least coin pay, plus an alternative algorithm should one of the coin tubes be empty and thus unable to dispense coins of that denomination.

The classic example was buying a 60 cent soda pop with a dollar (I know, pop was cheap back then ;-). This leaves 40 cents change, or in the US, 1 quarter, 1 dime, and 1 nickel for least coin pay. If the nickel tube were empty though, the machine would dispense 4 dimes.

I know to is not quite the lofty heights of academia, but it was an actual application of the problem's solution. On a further note, more modern coin changer mechanisms implement their own coin management so for those more capable peripherals, we would just let the coin mech figure out if change could be made.

If not, the customer would get the dreaded NO CHANGE error message and the money would be returned.


Colored cliques complexity Given:

graph with colored edges;
list of $\alpha$ colors;
list of $\epsilon$ colors;
clique size $k$.

Problem:

Do all edges colored in one of $\alpha$ colors are members of cliques with size $k$?
Isn't there an edge of some of $\epsilon$ color that is not contained in clique of size $k$?

Example:

Given some graph that has blue, red, green and magenta edges.

$\alpha$ colors: red, blue.

$\epsilon$ colors: green, magenta.

Answer is yes if both conditions are satisfied:

All red and blue edges are contained in cliques of size $k$ (or larger, of course).
There exists at least one green and at least one magenta edges that are contained in some cliques of size $k$.

Here are 2 special cases, for both $n = 10, k = 4, \alpha$: red and blue, $\epsilon$ - green and magenta. The only difference is color of edge BE.

1st graph satisfies the conditions: all red and blue edges are contained in 4-vertex cliques ABIH, FGIJ, CDEF as well as they contain at least one green and at least one magenta edge.

2nd graph doesn't satisfy the conditions because blue edge BE is not a member of 4-vertex clique.

I think this problem is PSPACE-complete but I'm not sure about reduction from TQBF to this. If such reduction is possible, it is not similar to known SAT to max-clique reduction.

Your problem is in NP.  (A certificate for a "yes" answer is to list one of the $k$-cliques that each edge is contained in.)  Therefore, it's not likely to be PSPACE-complete: if it were PSPACE-complete, that would imply NP = PSPACE, which would be surprising.

Your problem is NP-complete.  It is at least as hard as the $k$-clique problem. Suppose we have a graph and we want to know whether it contains a $k$-clique.  Then we can color all edges green, let $\alpha$ be the empty list, and let $\epsilon$ be the list containing only the color green.  Now the graph has a $k$-clique if and only if the answer to your problem is yes.  But testing for a $k$-clique is NP-complete, so it follows that your problem is NP-complete too.


Computational Complexity of Solutions of the Traveling Purchaser Problem on a Small Data Set I have encountered a problem that is essentially the textbook statement of the Traveling Purchaser Problem.  I don't know if this is the proper place to put this, if not then I will delete it.

Also a note is that while I have done some studying on my own of computer science, I did not have much formal education in it.  I do have a reasonably strong math background though.

Now on to the background of the problem:

I know the Traveling Purchaser Problem is NP-Hard, and thus there is no optimal solution algorithm known.  I know that as such, there are many different solution algorithms, of varying efficiency.  The (admittedly few) papers that I have seen though use this on sets of 100s of nodes,  and don't explicitly state the complexity of the algorithm in terms of big-O notation or similar functions.  Since my data set is relatively small (7 nodes and about 50 items to purchase).  I was wondering if it might be a waste of time to implement a complex, if efficient, algorithm.  But that is not my question, as I think such questions would be out of place here, it is just the background.

My question is the following:

What are some of the common algorithms for approximating the solution to the Traveling Purchaser Problem along with their computational complexity in terms of the number of nodes and the number of items to purchase.

First, it is good to observe that the problem is very difficult to approximate (see e.g., my earlier answer on it here).

Second, there is very recent survey on the traveling purchaser problem and its variants by Manerba et al. [1]. Essentially, you will find discussion on relevant methods that have been applied to solve the problem in practical settings. If you want theoretical time bounds for heuristics, see Section 6.1.1. on page 13.

[1] Manerba, Daniele, Renata Mansini, and Jorge Riera-Ledesma. "The traveling purchaser problem and its variants." European Journal of Operational Research 259.1 (2017): 1-18.


DFA for $L = \{y \in (a+b)^* \mid ||y|_a - |y|_b| \leq 10 \}$ $L = \{y \in (a+b)^*  \mid  ||y|_a - |y|_b| \leq 10 \}$

Any idea? I have problem with this kind of task.

I am afraid that you cannot construct a DFA for $L$ since it is not regular.

Intuitively, a finite automaton cannot even make sure the number of $a$'s and the number of $b$'s are the same since its finite memory cannot keep track of the number of the $a$'s in the initial part of $a^nb^n$ when $n$ become sufficient large.

How to prove that  language is not regular?

Use the pumping lemma. For example, what about a word that barely satisfies the condition such as $a^pb^{p+10}$?

Use Myhill–Nerode theorem. How about elements $a^n$ for all $n$? Does any of two of them belong to the same Myhill–Nerode class?

Exercise 1. Let $\lfloor x\rfloor_a$ be the minimum number of consecutive $a$'s in $x$ and $\lceil x\rceil_a$ be the maximum number of consecutive $a$'s in $x$, where $x\in\{a,b\}^*$ contains $a$. $\lfloor x\rfloor_a=\lceil x\rceil_a=0$ if $x$ does not contain $a$. Is the following language regular?
$$L = \{x \in \{a, b\}^*  \mid  \lceil x\rceil_a - \lfloor x\rfloor_a \le 10 \}$$

Exercise 2. Is the following language regular?
$$L = \{xy \mid x,y\in \{a,b\}^*  \wedge ||x|_a - |y|_a| \leq 10 \}$$


Lower Bound for Comparison-based sorting algorithms We know that the lower bound for comparison-based sorting algorithms is Ω(nlogn), where logn being the binary logarithm of n. But what about for the best-case scenario of the bubble sort, which takes O(n) time? Of course, n is faster than nlogn. Why is that?

However, I don't know if this bound only applies for the worst-case scenario. I haven't ever learned the lower bound for the best- or average-case scenario. Is it different from the other?

(This question comes from the http://cstheory.stackexchange.com)

The lower bound of sorting algorithm comparison based is $O(nlogn)$.
The best case lower bound is $O(n)$ which comes from fact that you need to check if numbers are sorted, so you traverse all of them to find out if they are ordered.

The lower bound is applied to all instances of problem, not just lucky particular case.


Machines in P undecidable? Given a Turing machine $M$, we say that $L(M) \in P$ if the language decided by the machine can be decided by some machine in polynomial time. We say that $M \in P$ if the machine runs in polynomial time. Note that there can be machines that run needlessly long but still decide a language in $P$. By Rice's theorem, we know that

$\{ \langle M \rangle \mid M \mbox{ is a Turing machine such that }L(M) \in P \mbox{ } \}$ is undecidable. Is it known whether:

$\{ \langle M \rangle \mid M \mbox{ is a Turing machine such that }M \in P \mbox{ } \}$ is also undecidable?

Here is a paraphrase of the proof in the cstheory answer. We reduce from the halting problem. Suppose that we are given a machine $M$, and we are to decide whether $M$ halts on the empty input. We construct a new machine $M'$ accepting a single input $x$, which operates as follows:

Let $n = |x|$.
$M'$ runs $M$ for $n$ steps.
If $M$ halted within $n$ steps then $M'$ runs a dummy loop taking exponential time $\Omega(2^n)$. Otherwise, $M'$ just halts.

Since Turing machines can be simulated with only polynomial overhead, if $M$ doesn't halt then $M'$ runs in polynomial time. If $M$ halts, then $M'$ takes exponential time. Hence $M$ halts iff $M'$ is not polynomial time.

More generally, this shows that even if we know that $M$ runs in time at most $f(n)$ for some superpolynomial time-constructible $f$, then we cannot decide whether $M$ runs in polynomial time.


How to transform Nondeterministic finite automaton (NFA) to regular expression equivalent Im struggling to understand how to transform Nondeterministic finite automaton (NFA) of the following form:

To a regular expression equivalent. What I have tried was using arden's rule. However I just cant figure out how to simplify and return the appropriate regular expression corresponding to that NFA.

First I have created the initial equation corresponding to those states:

$1: q3 = q_1 0 + q_1 1$

$2: q1 = q_0 0 + q_1 1$

$3: q0 = q_0 0 + q_0 1 + \epsilon$

Which I have tried to simplify:

$1: q3 = (q_0 0 + q_1 1)0 + (q_0 0 + q_1)1$

$1: q3 = q_0 00 + q_1 100 + q_0 01 + q_1 11$

$1: q3 = q_0(0+1) + q_1(0+1)$

$2: q1 = q_0 00 + q_0 10 + \epsilon 0 + q_0 01 + q_1 11$

$2: q1 = q_0(0+0+1)+ \epsilon 0 + q_1 11$

$3: q0 = q_0 0 + q_0 1 + \epsilon$

$3: q0 = q_0(0+1) + \epsilon$

Here I just lost. Maybe there is a different approach suitable in this context.

Appreciate any help!

The Arden's rule, as it is usually stated, is easier to use if you consider equations on $(L_q)_{q\in Q}$ depicting the language $L_q$ the automaton accepts from state $q$. Doing this, you obtain the following equations. Check that you understand this properly :

$L_0 = 0L_0 + 1L_0 + 0L_1$
$L_1 = 0L_3 + 1L_3$
$L_3 = \varepsilon$

(I use $L$ instead of $q$ as it looks less misleading to me)

Once you have those equations, you can solve this as follows

$L_1 = 0 + 1$ (I replaced $L_3$ with its value)
$L_0 = (0+1)L_0 + 0(0+1)$ (Replaced $L_1$ and factorized. This is ready for Arden's rule)
Since $\epsilon\not\in L_0$, from Arden's rule : $L_0 = (0+1)^*0(0+1)$

The language accepted by the automaton is always the union of the $L_{q_i}$, where the $q_i$ are the initial states. So here, $L = L_0 = (0+1)^*0(0+1)$


How can this grammar parse such an input? I've an example which I simply don't get at all.

  Implement an attributed grammar that checks that either

  the word ends in $b$ or
  each prefix of the word contains at least as many $b$s as $a$s

  E.g. the word $bbbbaabaabaa$ is allowed but $abbabaabba$ is not. (I know - what an example!)

However, the grammar looks like this:

  \begin{align}
V &\rightarrow S \\
S_0 &\rightarrow S_1 a \\
S_0 &\rightarrow S_1 b \\
S &\rightarrow \epsilon
\end{align}

and I am allowed to extend it to an attributed grammar. But I can't imagine how this can even be parsed from those rules since removing element by element from e.g. $abbab$ will never end up such that a rule can be applied.

What am I missing here?

In an attribute grammar one assigns values to the nonterminals of the grammar. This is to help evaluating parts of a grammar that are not context-free. One of the simple types is inherited attributes, these are assigned bottom-up in the derivation tree.

The indexes $S_0$ and $S_1$ are used here to distingish different occurrences of the nonterminal $S$ in the grammar. A good choice for an attribute here would be the difference of the number of occurrences $b$ and $a$. This number should never be negative according to your specification. I do not know how you are supposed to denote this, but assume the attribute is called $N$. For the rule $S_0 \to S_1 a$, the value of $N$ for $S_1$ determines the value of $N$ for $S_0$: $S_0.N = S_1.N - 1$ (since $S_0$ has one more $a$ than $S_1$.

Similarly for the other rule that introduces a $b$.

Now we have to introduce another attribute. In the end we should test whether the last symbol derived is a $b$. So the attribute should remember that letter and test it in the last step $V\to S$ (this is the last step in a bottom-upevaluation).

Again: check your class notes on how to specify alle these details.

Your examples are not clear: $aa$ does not end in a $b$ and neither has it at least as many $b$'s (?!)


Are expert systems outdated, what are better alternatives to them, if any? I need to link facts to actions through rules. If a person bought soup 10 times and he is coming at midday every day, then the system should link the fact that the person bought soup so many times, using the rule "person, consecutively buying soup 5 or more times within a month is going to buy soup with 90% confidence", to the conclusion that with 90% confidence today at midday, the same person will show up, ordering soup.

Above is an example of an expert system, however based on the research I've just done, it seems like expert systems have lost their popularity, which they had in 90s-00s. The only "popular" applications are business decision making and some medical systems. I am wondering if I should use expert systems or should I look into more "advanced" alternatives? What are the obvious disadvantages to using an expert system, besides the setup cost of conducting the research?

Expert systems went through a phase of increasing acceptance and then widespread recognition of their limitations (see Wikipedia). There are many references that consider cons e.g. Problems in expert system development (Kemp, 1993).
In more recent years recommendation systems have taken over some of the function you describe in recommending products to customers. A notable development or historical event was the Netflix contest for movie recommendations which led to a burst of innovation and interest in the area. Another aspect of your question involves learning patterns of human behavior and this can be done with ANNs and similar technology.


Converting a special case TM to a regular TM So, I have been given a TM where the head can access and write both the character that the head is pointing at and the next character to the right.
So if we have a TM abbb and the head is pointing at a, it can access and write into the the next character also ie the first b. So it has access to both the first and second characters of the string abbb. How would I show that this isn't actually a special TM but can be done with a regular TM too?

You want to show that this modified Turing machine is equivalent to the standard definition of a Turing machine, that is for every modified Turing machine $T'$ there exists a standard Turing machine $T$ such that $L(T')=L(T)$, and vice versa.
It is easy to show that for every standard Turing machine $T$ there is a modified Turing machine which accepts $L(T)$, just don't use the modified machine's ability to read or write to the input to the right of its head. Then these modified Turing machines are at least as powerful as standard Turing machines.
Now if $T'$ is a modified Turing machine which can read and write to the character immediately to the right of its head, we want to show that there exists a Turing machine $T$ which recognizes the same language as $T'$. Formally this gets a bit messy but the idea is whenever $T'$ would read or write an input from the cell to its right we add a sequence of states and transitions in which $T$ will move back and forth between the cell it is currently over in $T'$ and the cell to its right in $T'$ reading and writing as $T'$ does, then $T$ will move to the position and state specified in the transition function of $T'$. Essentially, if $T'$ reads from the cell to its right, $T$ will move to the right, read the input then move to the left. If $T'$ will would to the cell to its right, $T$ will move to the right, write the same thing $T'$ would have written, then move back, and transition to the same state $T'$ would have transitioned to.


Has category theory had an impact on computer science? I've only learned bit of category theory, but so far its relation to type systems seems mostly descriptive. For example, you really don't need to know about coproducts to come up with the idea of union types.
I'm looking for references to ideas in computer science that were arrived at due to results in category theory. I'd be especially interested in results in areas other than PL such as machine learning.

Categories can be used to model databases, and have been used for data integration. See also this paper. There's a pretty gentle introduction in chapter 3 of Seven Sketches in Compositionality.
Coalgebras are a generalization of automata, and have provided insight into notions of bisimulation. I saw a talk about this, but also found this paper
Closed symmetric monoidal categories have been used to model linear logic, but also to model quantum computation (which is itself related to linear logic). There's a Rosetta Stone paper that discusses this.
CRDTs are a cornerstone of distributed computing, and while I don't understand it myself, it looks like there is some connection to category theory
Guarded recursion and the Topos of Trees generalize step-indexing, which has been used to model higher-order separation logic. This is a tool for verifying programs with heap memory and/or concurrency, and has been applied in Iris.

I think it's also worth mentioning that the Programming Language concepts are not exactly isolated or esoteric. Monads originated in Category theory: my understanding is that Moggi (a category theorist) first applied them, and they were brought into Haskell by Philip Wadler.
But, monadic interfaces are everywhere. Errors in Rust are monadic, as are basically any langage's Option type. Promises in Javascript are monads. Using monads gives a beautiful implementation  of Software Transactional Memory, a lock-free approach to concurrency.
And, of course, category theory is basically at the heart of modern logic research, which underlies most CS theory.


Shortest path in NL algorithm, need help to understand https://people.eecs.berkeley.edu/~luca/cs172-07/solutions/sol8.pdf

I'm checking those solution and i'm having trouble understanding the proof that shortest path belong to NL (2.a).

So being Shortest path = {(G=(V,E), k, s, t) | shortest path from s to t in G has length k}  and rk-1 being the number of vertices reachable in k-1 steps, the proposed algorithm is

d ← 0
flag ← FALSE
for all w ∈ V do
    p ← s
    for i ← 1 to k − 1 do
        non-deterministically pick a neighbor q of p
    if p = w then
        d ← d + 1
    if w = t reject
    if w is a neighbor of t then
    flag ← TRUE
if d < rk−1 reject
if flag then accept else reject

In a line it does "non-deterministically pick a neighbor q of p" but q it's never used. Where and how it's q used?

What is probably meant is that the chosen vertex is substituted back into $p$. This way when the for loop is done, $p$ contains some vertex of distance at most $k-1$ from $s$. Note that comparing the counter $d$ to $r_{k-1}$ makes sure that you went over all the vertices of distance at most $k-1$ from $s$.


Big-O notation for Polynomial Time Complexity Recently we had a quiz where one of the question were -
Q: Asymptotic notation for polynomial :

 - 2^Ο(n)
 - Ο(n log n)
 - n^Ο(1)
 - None of these

I know that Polynomial time complexity is $\mathcal{O}(n^c)$, where $c$ is an arbitrary constant.

But then I checked it up on Wikipedia, and it got me confused.
According to Wikipedia, Polynomial Time Complexity is $2^\mathcal{O(log n)} = poly(n)$, where  $poly(x) = x^\mathcal{O(1)}$.

So my questions are -

What is the $Big-O$ notation for Polynomial Time Complexity
and how is it $2^\mathcal{O(log n)} = poly(n)$ ?
What will be the answer for the quiz ?   I have answered None of these .

Also it has got this line - In the table, poly(x) = x^O(1), i.e., polynomial in x.

What does polynomial in x means ?

The question is worded in a tricky way. When it says "polynomial" it really means "all functions that represent a polynomial complexity class". Essentially, they want the asymptotic notation for the functions $f(n)=1$, $f(n)=n$, $f(n)=n^2$, etc. The reason we want this is because you would see this inside big-O like $O(1)$, $O(n)$, $O(n^2)$, etc. Those functions represent these big-O sets.
The reason we talk about it this way is because we are talking about it in the world of complexity classes. An example is $P$.
\begin{align}
P = DTIME(poly(n)) = \bigcup\limits_{k\in\mathbb{N}}DTIME(n^k)
\end{align}
From the wiki on DTIME.

If a problem of input size $n$ can be solved in $O(f(n))$, we have a complexity class $DTIME(f(n))$ (or $TIME(f(n))$).

So the asymptotic notation for the set of these functions is $n^{O(1)}$. The following is a way to reason about it.
\begin{align}
n^{O(1)}
&= n^{\{0,1,2,...\}} \\
&= \{1,\ n,\ n^2,\ ...\}
\end{align}
To show that $2^{O(\log n)} = poly(n)$ is with the same reasoning as above.
\begin{align}
2^{O(\log{n})}
&= 2^{\{0\cdot\log{n},\ 1\cdot\log{n},\ 2\cdot\log{n},\ ...\}} \\
&= 2^{\{0,\ \log(n^1),\ \log(n^2),\ ...\}} \\
&= \{2^0,\ 2^{\log(n)},\ 2^{\log(n^2)},\ ...\} \\
&= \{1,\ n^1,\ n^2,\ ...\} \\
&= n^{O(1)}
\end{align}
To formally show these are equal, you would have to use set notation.
Finally, "polynomial in x" means that $poly(x)$ grows polynomially depending on $x$. You can see that some of the entries in the table have a function as the argument to $poly$. For instance, $poly(\log{n})$ (polylogarithmic) grows slower than $poly(n)$ (polynomial) since $O(\log{n}) < O(n)$.


Synchronizing sequence and Synchronizable DFA, how come states repeat if synchronizing word length is $>|Q|^{2}$? I am trying to prove problem 1.59 in Sipser's book: Introduction to the theory of computation , 2nd Edition.

Let $M=(Q,\Sigma,\delta,q_0,A)$ be a DFA and let $q'$ be a state of $M$ called its "home". A Synchronizing sequence for $M$ and $q'$ is a string $s\in \Sigma^*$ where $\delta (q,s)=q'$ for every $q\in Q$. (We actually have extended $\delta$ to strings so that $\delta(q,s)$ equals the state where $M$ ends up when $M$ starts at state $q$ and reads input $s$).
Say that $M$ is Synchronizable if it has a synchronizing sequence for some state $q'$.
Prove that, if $M$ is a $k$-state synchronizable DFA, then it has a synchronizing sequence of length at most $k^3$.

This problem was already attempted here. I don't understand the answer though:

The proof of this a standard shrinking argument: if such a word is longer than $k^{2}$, then during the runs from $q1$,$q2$ a pair of states repeats, and we can shrink $w$.

How come a pair of states repeats?
I don't see a problem with runs from $q1$ and $q2$ reaching separate states. I don't so how I could be sure that I could shrink to word without disturbing both routes.

synchronously moving through the DFA beginning with two different states while an input of a word w can be described as choosing two states out of k on every step. So there exist $\binom{k}{2}$ possibilities to do that.
As $k^2>\binom{k}{2}$, there will be one step where we choose a pair of states which we already had before. So the word $w$ can be shortened: this is the contradiction to the claim that the word is longer then $k^2$.


Lower bound for sorting n arrays of size k each Given $n$ arrays of size $k$ each, we want to show that at least $\Omega(nk \log k)$ comparisons are needed to sort all arrays (indepentent of each other).

My proof is a simple modification of the decision tree argument used to obtain the lower bound for comparison-based sorting of one array. More specifically, I argue that there are in total $k!^n$ possible permutations for the entries in all given arrays, and that a binary tree with that number of leaves is of height $h \in \Omega(nk \log k)$. Is that argument correct?

Furthermore, I was told that merely observing that one needs $\Omega(k \log k)$ comparisons for each of the arrays and we need to sort $n$ times in total (for $n$ arrays) is not a sufficient argument. Why is that? My answer would be that this is just one possible approach to this problem, and not a general argument excluding each and every other potential comparison-based algorithm for solving the given task with less than $\Omega(nk \log k)$ comparisons.
However, this is not particularly concise and I would consider a rather technical argument (which I don't see) as more appropriate. What would that be?

For the first part, as the comments suggest - observe that there are $k!^n$ possible permutations for the inputs - indeed, every array has $k!$ permutations, and there are $n$ arrays, so you have $k!$ options for the first array, $k!$ for the second, and so on.

So the height of a decision tree is
$$\log (k!^n)=n\log (k!)\in \theta(nk\log k)$$
So you need at least that many comparisons in order to determine a single leaf.

For the second part - the argument you suggest is quite close to a formal explanation.
The lower bound of $\Omega(k\log k)$ is for comparison-based algorithms that compare elements in the array. When you have several arrays, then it is not justified to assume that sorting them is equivalent to sorting each one independently.

A-priori, it may be easier to sort them by comparing elements between the arrays. But the lower bound on sorting does not utilize such a setting, so it is not directly relevant for this problem.

In my opinion, this is as formal as you can get without formally defining what a comparison-based algorithm actually is. To define the latter, you need to formally model the computational model you use (which would be a sort of pointer-machine), and this is unlikely to result in any insights other than what you already mentioned.


Understanding time complexity of a while loop that will look over all vertices and edges I need a little clarification on differing time complexities. My analysis for the below algorithm was $O(n +nm)$, but the correct analysis would be $O(n+m)$. I know that Color takes $O(n)$ time to initialize and the inner for loop takes $\mathrm{deg}(v)$ time, which by the handshaking lemma, wouldn't the inner for loop then be $O(m)$ and since the outside while loop iterates over all vertices in worse case so shouldn't that be $O(n)$, Giving $O(n) + O(nm)$?

Because each edge contributes to two degrees, we have
$$\sum_v\mathrm{deg}(v)=2m.$$

The time taken by the whole loop is $O(m)$.

Your analysis is of course correct, but since you replace $\mathrm{deg}(v)$ with the upper bound $m$, you get a loose bound finally.

By the way this is BFS if you ignore the "color" action.


What is the consequence of $\oplus P\neq PP$? From $P\subseteq \oplus P \subseteq PSPACE$ and $P\subseteq PP \subseteq PSPACE$ we infer $\oplus P\neq PP$ gives that
$$P\neq PSPACE.$$

Are there any other consequences?

Turns out, you are immediately able to separate $\mathrm{P}$ from $\mathrm{PP}$.

Assuming that $\oplus\mathrm{P\neq PP}$ but also assume to the contradiction that $\mathrm{P=PP}$, then $\mathrm{P^{PP}=P}$. But $\oplus\mathrm{P\subseteq P^{\#P[1]}=P^{PP}=P}$. So, $\oplus\mathrm{P=P=PP}$ violating our assumption and concluding our proof by contradiction.


Necessity to define co-NP in the first place? I've recently started to deal with complexity theory and I'm trying to wrap my head around all the definitions and why they make sense.

One thing I don't quite understand is the importance/necessity of co-NP as its own set/class of problems. Couldn't for example TAUT be classified as a NP-complete problem just like SAT or is there some specific motivation to not put complements of a problem in the same set as the problem itself?

I'm sorry if this has been asked before or if my question is silly and doesn't make sense at all (In this case I'd like to know why if possible), I've really tried to look for it beforehand on the internet.

Kind regards,

We don't define problems to be NP-complete. We define classes of problems, define the concept of completeness for those classes, and then prove that problems are complete, because they have the properties that define completeness.

Analogously, we don't define 13 to be prime; rather, we define the property of being prime and then prove that 13 has that property.


Matching superimposed image We are given two grayscale images, one of which contains a large, mostly contiguous patch from the other one. The patch can be altered with noise, its levels may be stretched, etc.
Here's an example

We would like to determine the region of the image which was copied onto the other image.
My first instinct was to look at the local correlation. I first apply a little bit of blur to eliminate some of the noise. Then, around each point, I can subtract a gaussian average, then look at the covariance weighted by that same Gaussian kernel. I normalize by the variances, measured in the same way, to get a correlation. If $G$ is the Gaussian blur operator, this is:
$$ \frac{G(A \times B) - G(A)G(B)}{\sqrt{(G(A^2)-G(A)^2)(G(B^2)-G(B)^2)}}$$
The result is... not too bad, not great:

Playing with the width of the kernel can help a bit. I've also try correlating Laplacians instead of the images themselves, but it seems to hurt more than it helps. I've also tried using the watershed algorithm on the correlation, and it just didn't give very good results.
I'm thinking part of my problem is not having a strong enough prior for what the patch should be like, perhaps a MRF would help here? Besides MRF, are there some other techniques, perhaps more lightweight that would apply? The other part is that correlation doesn't seem to be all that great at measuring the distance. There are places where the correlation is very high despite the images being very visually distinct. What other metrics could be of use?

I will assume the patch is the same position and is unchanged.  Given this, you could try a two-step procedure with basic image processing methods:
Step 0 (optional): Align/register the two images.
Step 1: Compute local image similarity, on a pixel-wise basis.
Step 2: Find a large connected region in that similarity map where there is high similarity.

For Step 1, one approach is local correlation, as you used.  You could also try normalized cross correlation if you think one image might be shifted slightly (e.g., by a subpixel amount).  Another is to compute the square of the pixelwise difference of the two images.  Yet another possibility: at coordinate $(x,y)$, extract a patch 7x7 patch from each image centered at $(x,y)$, compute some measure of image similarity (e.g., L2 distance, local correlation, you name it; possibly preceded by some image registration step) between those two patches, and use that as the similarity measure at $(x,y)$; do this for every coordinate.
For Step 2, you are looking for a large connected region with a high similarity score.  One approach is to threshold followed by connected components.  Another approach is a watershed transform.  Another approach  is to use image morphological operators (e.g., opening) followed by one of these methods.  More generally, you could look at methods for blob detection.
With image processing tasks like this, you may need to experiment with a bunch of different methods and see which ones work well.  When you experiment, I recommend that you implement, measure its effectiveness, also look at a random sample of 5-10 images and the results of the analysis on those images, and look at a random sample of 5-10 images that got handled incorrectly.  This visualization can be helpful in understanding in what situations a method fails, which can sometimes suggest improvements to address those particular situations.


Image Comparison tuned to Human Perception Say I have two systems that take the same drawing commands and starts drawing on their respective platforms (i.e. HTML Canvas). After this is done, I want to save and compare these two images to ensure that they are perceptually the same, even though the shapes and colors may be very slightly off (non-perceptible differences).

I tried using perceptual hashes, but unfortunately it does not seem sensitive enough for this task. So for example, if you set 1000 pixels all black (for an image that is 1920x1080) on one and compare it to the other, it will be very obvious perceptually but the pHash algorithm will still return a 100% match.

I tried using nearest neighbor averaging for all pixels. Basically, for each pixel, I averaged its value with that of a number of its neighbors and set this value back to the pixel. This seems to work well with shapes that have hard edges and straight lines, because it only takes a very small localized change for it to be perceptibly different. For long curves, this is not so good since there can be moderate changes throughout the entire curve with it still being considered perceptually the same.

Does there exist an algorithm that can handle perceptually small changes in many possible shapes/curves? Should I use multiple algorithms to handle this task?

Unfortunately there is not likely to be any good general algorithm for this.  Human perception is extremely complex.  The best you can do is find algorithms that will sometimes recognize two images as perceptually similar, but there will inevitably be some pairs of images that humans would classify as perceptually similar but your algorithm won't detect as similar.

Your best bet is probably to try to find out exactly what minor differences tend to be introduced by these particular platforms, and then try to devise an algorithm that is tuned to those particular kinds of differences -- you'll probably have better luck than that than with any general algorithm.

One very simple algorithm is to align the two images (e.g., using SIFT/SURF/etc.), add a bit of Gaussian blur to the two images, downscale, and then compare using a L2 norm.  Another simple algorithm is to align the two images with SIFT/SURF/etc., and then compute a metric based upon the number of inliers vs outliers in the feature points (how well the set of feature points from the first image match up with the set of feature points from the second image).  However, it's hard to know how well this will work for your particular application, without knowing the details of the differences that tend to arise in your situation.


maximum Hamilton cycle and NP-completeness we know max tsp (maximal Hamilton cycle) is NP-Hard. is there any decision version for this problem to conclude this is NP-Complete?

A decision problem is NP-complete iff it is in NP and it is NP-hard.
The decision version of Max-Hamiltonian cycle would be "given a weighted graph $G$ and a value k, decide whether there exists a Hamiltonian cycle of weight at least $k$ in $G$".
Your problem is clearly in NP (since a yes-certificate is the sought Hamiltonian cycle). Moreover it is also NP-hard since it is a generalization of the classical Hamiltonian cycle problem on unweighted graphs (simply set all edge weights to $1$ and $k=n$ to obtain an instance of your problem).
We can then conclude that this problem is NP-complete.


A string representation of any Turing machine The set of all Turing machines is said to be countable. The central idea of the proof of this fact is that every Turing machine can be written as a finite string of characters. I am having trouble seeing how this could be true.

If we formally define a Turing machine as having a tape language $\{0, 1, \sqcup, x\}$ and input language $\{0, 1\}$, then I can sort of see how any Turing machine could be encoded.

However, many books allow other symbols, such as $a$ or $3$, etc., to be part of the input language. I've heard people say that this is okay because we could represent such characters as a string like $0101$ or $1011$ or whatever, much like how Unicode represents code points consisting of multiple code units, or just how any computer represents anything at all!

But here is my problem with this. If we are trying to construct an actual function $f$ from the set of all Turing machines $\mathscr{M}$ to $\mathbb{N}$, then every Turing machine must be encoded in the same way. That is, we can't have encodings of different lengths, so that 01 represents $01$ for one Turing machine and represents $3$ for another. That is, unless we have some encoding at the beginning of each Turing machine which explains how the machine is to be decoded. But even then, this encoding itself must be universal.

The problem is much like the charset problem for HTML pages. That is, that a web browser must know the encoding of the page before it can decipher a command in the HTML to encode the page a certain way. This was solved for web pages by having the encoding command characters (meta charset=utf-8 for example) be the same in all encodings. But then the encoding itself is stored elsewhere.

Anyway, my question is how we resolve this apparent conundrum. How does one encode a Turing machine with a finite input language of any length so that one can make one function from $\mathscr{M}$ to $\mathbb{N}$?

Consider a Turing machine with $n$ tape symbols and $m$ states. We can assume that the symbols and the states are ordered, so that we can talk about the first, second, ..., $n$th tape symbol, and the first, second, ..., $m$th state. (This is similar to your idea of counting Turing machines up to isomorphism.) So without loss of generality, the tape alphabet is $\{1,\ldots,n\}$ and the states are $\{1,\ldots,m\}$. We will encode this Turing machine as the following sequence of statements in English: (the notation $\langle n \rangle$ means to replace $n$ with its decimal representation)

The number of tape symbols is $\langle n \rangle$.
The number of states is $\langle m \rangle$.
The starting state is $\langle s_0 \rangle$. [Replace $s_0$ with the starting state]
The accepting states are $\langle s_1 \rangle$, ..., $\langle s_k \rangle$. [Replace $s_1,\ldots,s_k$ with the accepting states]
When in state 1, upon reading symbol 1, write symbol $\langle \sigma \rangle$ and move $\langle D \rangle$ [Replace $\sigma$ with the tape symbol and $D$ with either "left" or "right"]
...

This is a description in English over a finite alphabet. In particular, it can be represented in ASCII. So there are only countably many descriptions.

As usul mentions, we tacitly assume that the underlying representation of everything in mathematics is a set, just like the description of everything in computers is in binary. Not all sets are finite, but if you only use hereditarily finite sets, then you can avoid forcing the tape alphabet to be $\{1,\ldots,n\}$, and instead allow arbitrary hereditarily finite sets. However, that doesn't buy you anything (unless you care about this point for philosophical reasons).

More generally, you might be worried that when I describe a Turing machine I use the symbol $\diamond$, a symbol not covered by the above (it's a set-theoretic "atom"), so this Turing machine doesn't have a description in my formalism. To counter this, I suggest you provide the description of your Turing machine as a LaTeX document (which is what I used when describing the machine in the first place). LaTeX has a finite alphabet (or finitely many possible finite alphabets), so again everything is countable.


Practice of setting parallelism as the default behaviour This is a soft, and probably also an opinion based question.
Suppose I am writing a library in C++ for the purposes of working with financial data. My goals are:

Since I work with big data, I want to make it as fast as possible by using parallel computing principle inside the functions.
I want my colleagues to use this library without understanding/tweaking the parallelism underneath the functions.

The resulting questions are:

Is this a good idea to make parallelism the default behaviour? For instance sum(vector) to parallelise the summation without asking the user.
If yes, is there any rule of thumb that would cover the default behaviour of the task split between the processors? I.e. how many processors I should use?

Thanks in advance.

Have fun. If you use multiple threads you need to make sure that the overhead doesn’t outweigh the savings. The number of processors to use depends on the number of available processors, their properties (hyperthreading, performance vs. power saving), and the usage of the machine including the OS. And making one task fast may have negative side effects on the machine as a whole. Summary: It’s difficult.
Set your priorities: First make it work. Second make it maintainable. Third if required measure to find performance problems and fix them by using code that is not stupid (in the last ten years 99% of my performance problems were caused by stupid code and fixed by using code that isn’t stupid), then by using good code, then by using optimised vector code. Using multiple threads should be your very last resort.


Are there any examples of projects running a program that will take many years to finish its job? There are algorithms that are said to be unfeasible to be applied in practice due to their time complexity. In textbooks, it's common to see remarks like "it would take hundreds of years" about using them. Unfortunately, it's often the case an inefficient algorithm is the only proven solution for an interesting problem.
Is there an example of a project running one of those algorithms where the participants know they won't be around to see the results hoping to solve a problem for the next generations?

There have been several programs running for very long times, like the Great Internet Mersenne Prime Search, which has been going for some 25 years now.


Merge-by-weight to solve reachability problems in trees and DAGs Let $T = (V, E)$ be a tree with a designated root $r \in V$. The fact that the tree is rooted allows us to speak of "subtrees of $T$ rooted at some node $x \in V$". Let's say we have a (not necessarily injective) function $c: V \rightarrow \mathbb{N}$ that assigns a color to every node.

We want to find for every node $x \in V$ the number of distinct colors in the subtree rooted at $x$. So if $A(x)$ is the set of children of $x$, we want to find for every node $x$, the cardinality of the set

$S(x) = \bigcup_{y\in A(x)} S(y) \cup \{c(x)\}$

There is a rather simple algorithm that solves this problem offline in $O(n \log^2 n)$:

Process the nodes in depth-first order
Represent the sets $S(x)$ as a persistent, self-balancing binary search trees
For every node $x$, let $y \in A(x)$ be the child of $x$ that maximizes $|S(y)|$.  Now we just merge for every other child $z \in A(x) \setminus {y}$ the set $S(z)$ into the set $S(y)$ via insertion. We also insert $c(x)$ and now have $S(x)$ as a binary search tree and can give the answer for node $x$

We can even avoid the persistent trees by mutating the subresult for the heaviest child instead of creating a new set.

The typical argument I have seen to justify the bound is the following:

  A "move" consist of taking an element from a set and inserting it in another set.
  Let's prove that there's at most $O(n \log n)$ moves, each move can be done in $O(\log n)$, the total complexity is $O(n \log^2 n)$.

  When you are merging two sets you move all elements from smaller set (assume its size is $k$) to the bigger one, so every element in the smaller set now is in a set with at least size $2k$. In other words every element that has been moved $t$ times is in a set with at least size $2^t$, thus every element will be moved at most $O(\log n)$ and we have $n$ elements so in total there will be at most $O(n \log n)$ move operations.

(Quote from a Codeforces comment).

While this is a beautiful argument, it's not quite correct, because usually we remove duplicates, so sets don't in fact grow exponentially (for example if every node has the same color).

I am convinced that the bound holds, because I can prove it using structural induction. What I want to know is the following:

Is there a way to prove the $O(n \log^2 n)$ bound using an argument similar to the above, by bounding the number of "moves" of the color of a node? In other words, can the proof be "fixed" easily?
The argument from above would also hold in DAGs, not only in trees. However it seems unlikely that we could achieve a runtime better than $O(n \cdot m)$ to solve this problem in a DAG, so I guess there is no fix for the proof idea in this case. Am I right? Is there a good intuition for that?

There are two (equivalent) ways to fix the argument:

Start by not eliminating duplicates. Then the argument works. Then argue that removing duplicates can only decrease the running time.
Count elements with multiplicity, that is, consider each set $S(x)$ as a multiset.

Both of these arguments require a slight modification of the algorithm: for each vertex $x$, you keep track of the size of the subtree, and use this to select the heaviest child rather than the number of distinct colors.

This argument breaks down for a DAG since a vertex can have multiple parents.


Solving equation with $n\log n$ Given a computer that takes 1 microsecond for an operation, I'm trying to find the amount of operations this computer can perform in one second, given an algorithm with complexity $O(n\log n)$. I've tried to solve it by the following ways but always get stuck. Note that one second equals $10^6$ microseconds.

I've found this post where it's stated that "there is no simple way" to solve that but I still want to ask here if there is any different approach to the question from a "computer science perspective".

No way to say. $T(n) = O(n \log n)$ means there exist constants $c > 0, N_0$ so that for all $n \ge N_0$ it is $T(n) \le c n \log n$. They are anything, i.e., it might be valid only for ridiculously large $n$ (large $N_0$), or even for small $N_0$, like $N_0 = 10$, the constant $c$ could be such that all you know is that $T(100) \le \text{one milisecond}$ or $T(100) \le \text{one week}$.


Relation between RAM and Turing machine Denote $D$ a set of finite sequences of integers. In Papadimitriou's "Computational Complexity" in theorem 2.5 it is proved that if a RAM program $\Pi$ computes a function $\phi$ from $D$ to integers in time $f(n)$, then there is a $7$-string Turing machine $M$, which computes $\phi$ in time $O(f(n)^3)$.

Consider the following example: $\phi(S)$ is a sum of first two numbers of a finite sequence $S$, or $0$, if $|S| < 2$. It seems to me that a RAM, defined in Papadimitriou's book computes $\phi$ in time $O(1)$. Thought, any Turing machine, computing $\phi$, should work for at least linear time (we can take an input of length $n$ with only two numbers in sequence). I don't see how to cope with this contradiction.

Could you please describe me, where I am wrong? Thanks a lot.

You're right, there is a missing assumption that f(n) is at least O(n).
Indeed, the last line of the proof state that the operand are of size O(f(n)), while what has been proven before is O(f(n)+l(I)+l(B)). Since l(I) is O(n), the hypothesis is needed for this simplification.


When to terminate search for path in an infinite grid I'm learning shortest path algorithms like Dijkstra's, BFS, etc. I understand on a 2D finite grid there are boundary conditions (i.e. size of the grid) that help terminate the algorithm and keep it in a certain scope/range. However when expanding this to an infinite 2D grid, I don't understand when (say using BFS as an example) to conclude that a path simple doesn't exist without having the algorithm run infinitely since I can't use grid size as a boundary condition. Is there some kind of formula that can be used in these cases? Also, take into account that there could be obstacles along the path too so the path distance can vary from different origins to destinations.

I've considered trying to take the absolute value of the difference between the coordinate points and raising it to some power as a way of setting an upper limit of steps taken before considering that a path must not exist, but this approach is obviously lacking and incorrect to say it bluntly since it doesn't work for many cases.

I apologize if my question is confusing. I'll restate it here: basically, how do I know when to assume a path from an origin to a destination doesn't exist in an infinite 2D grid?

Unfortunately, the simple answer is, you can't.

All the standard search algorithms have a runtime that's polynomial in the size of the graph. If your graph is infinitely large, there's no guarantee that they'll ever terminate for arbitrary inputs: how can they ever know whether they should give up now, or whether they'd find the answer if they just expanded one more node?

Any approach that involves putting an upper limit on the number of steps, is doomed to failure. Even if the start and end points are right next to each other in the coordinate system, I could delete the edge between them, then make it so that the shortest path from one to the other takes one more step than you're allowing. And then your algorithm will say, incorrectly, that there's no solution.

However, if you have additional information about your graph (perhaps there's only a finite number of edges missing from the grid?), then you can potentially exploit this to find an answer. It's only impossible for arbitrary infinite graphs; there are many classes of infinite graphs for which it can be solved.


Finding maximum of $n$ many $m$-bit integers Suppose you want to determine the largest number in an $n$-element set $X = (x_1, x_2, \dots , x_{n})$, where each element $x_i$ is an integer between $1$ and $2^m − 1$. Describe an algorithm that solves this problem in $O(n + m)$ steps, where at each step, your algorithm compares one of the elements $x_i$ with a constant. In particular, your algorithm must never actually compare two elements of $X$!
My thoughts: I thought about making intervals $[1,2), [2,4), [4,8), \dots , [2^{m-1}, 2^m)$ and somehow associate comparisons with these ranges. But, all of them were in vain. Would be welcome to hear your ideas on solving this!

Hi I make this post because this question is quite challenging for me and I want to know if my solution will pass "peer-review". Consider following algorithm for a RAM machine (// denotes integer division):
algorithm ArrayMax
Input: array $A$ of size $n$; $A[i] \in [1,2^m-1]$
Output: $max(A)$
left  <- 1
right <- 1
max   <- A[0]
while right <= A[0]: right <- 2*right
left <- right // 2
for i = 1...n-1:
    if A[i] <= left:
        continue
    if A[i] >= right:
        max <- A[i]
        while right <= A[i]: right <- 2*right
        left <- right//2
        continue
    while left-right > 1:
        mid <- (left+right)//2
        if max < mid:
            right <- mid
        else:
            left <- mid
        if A[i] < left:
            break
        else if A[i] >= right:
            max <- A[i]
            delta <- right-left
            left  <- right
            right <- left+delta
            break
return max

The algorithm operates by keeping $left \leq max < right$ and uses the bounds to make comparisons. Notice that if the bounds of $max$ aren't sufficient they are extended via binary search. How can one proof that this algorithm runs in $O(n+m)$? (This is not a rigorous proof; more an idea; if you have improvements please edit or write a comment)
I'll try to outline a proof using a potential function $\Phi(S_i)$ ($S_i$ is the state of the algorithm at iteration $i$). The Potential Method is usually used for data structures. We define:
$$\Phi(S_i) = \log2(left-right) \geq 0$$
There are two things that can happen between $S_i$ and $S_{i+1}$ (We only consider the worst case so we'll ignore the first "if" in the loop and focus on the second "if" and the while loop).
If the second "if" is triggered the following change occurs in the potential function:
$$\Phi(S_i) = j \rightarrow \Phi(S_{i+1}) \approx \log2(A[i]))$$
Also the cost of the operation is $T_i \approx \log2(A[i]) - \log2(right) \leq \log2(A[i]) - \log2(max)$
In the second case a binary search occurs which goes to depth $k$ (does $k$ bisections).
$$\Phi(S_i) = j \rightarrow \Phi(S_{i+1}) \approx j-k$$
Notice that the cost of bisecting is roughly $4*k$ comparisons. Thus the cost including the Potential Function is:
$$T_i = O(1) + 4k + 4(\Phi(S_{i+1})-\Phi(S_i)) = O(1) + 4k - 4k = O(1)$$
So basically the second case is for free. Lets now focus one the first case only. Consider that it happens $h$ times in a row. It is easy to see that for the second case to not occur $A[i+1] \geq 2A[i]$  Meaning we can approximate the cumulative cost with:
$$\sum_{i=1}^h \log2(2^{i+1}) - \log2(2^i) + (\Phi(S_{i+1})-\Phi(S_i)) = \sum_{i=1}^h 2(\log2(2^{i+1}) - \log2(2^i)) = \sum_{i=1}^h2(i+1-i) = 2h$$
Notice that since the the numbers are limited by $2^m$ we have $h \leq m$. Thus we obtain $O(m + n)$, where $m$ is accounting for the first cases and n is accounting for the second cases. Also the first while loop finding bounds for $A[0]$ runs at most $m$ times. I hope you get my idea, despite the fuzzy argument.


Regular expression for the language containing neither aa nor bb I want to create a regular expression for the language

$L=\{ w \in \{a,b\} |$ w has neither aa nor bb as a subword$\}$.

I've tried various things, but I can't seem to get the correct regular expression.

$((ab)^∗∪(ab)^∗a)∪((ba)^∗∪(ba)^∗b)$  will work.

The possibilities are: $a,ab,aba,ababa,...$ or $b,ba,bab,baba,...$ or empty string


Divide self-intersecting polygon into simple polygons My question is similar to question here Divide self-intersecting polygon

I have points of self-intersecting polygon, its edges and also I am able to find points where it intersects.

I have to divide it into simple polygons and tessellate them later.

I have an issue how we currently select the edge after the intersection point is encountered.
Right now we select an intersecting-edge which makes the smallest angle with the preceding edge.
This approach simplifies some intersecting loops (e.g. horizontal '8' is divided into two 'o' loops).

But this approach has some issue. Say two polygons one inside another. Such polygons are not divided into two loops.

I plan to select an intersecting-edge which makes the largest angle with the preceding edge. This way I can get the outermost loop first and than I will form the internal loops with remaining edges.
This will solve the problem for 'two polygons one inside another'. (This will fail for cases such as 'horizontal '8''. But this is OK as such case is handles while tessellating polygon)

Are there any known/unforeseen problems with this approach?

A self-intersecting polygon induces a plane partition, which should be represented by some data structure. This structure should include at least three types of objects - vertices, edges and faces. The faces are what you are trying to construct.

This data structure is called DCEL and it usually represents both planar graphs - the original graph with vertices and edges (where intersection points are added as new vertices, and some edges are split), and a dual graph with polygonal faces as vertices. Each vertex in the original graph should refer to a list of adjacent edges (sorted by angle, yes) and each vertex in the dual graph should refer to a list of adjacent edges, forming its boundary. Edges are usually represented by two arcs with orientations, opposite to one another. In this case each arc is adjacent to exactly one face (including the exterior face), which normally lies "to the left" of it.

Having this data structure implemented you'll be able to calculate all the faces by finding proper cycles in the set of all arcs.


Help with understanding Hopcroft's algorithm So I wrote an implementation of Hopcroft's algorithm. While testing, I discovered that it would sometimes produce an automaton that wasn't equivalent to the original. At first, I figured it must be a bug in my code, but after going over the algorithm by hand with a small example, it seems to be a bug in my understanding of the algorithm. Can someone help me correct my understanding?

Here is the algorithm, copied from the paper "Re-describing and algorithm by Hopcroft" by Knuutila. (This version differs a little from the one on Wikipedia, but I have essentially the same problem with that one too.)

let P = {F, F^c}, where F is the set of accepting states
let W = {(F, x) for every x in the alphabet}
while W is non-empty:
    remove an arbitrary element (A, x) from W
    let X be the set of states that move into A on input x
    for every Y in P that intersects non-trivially with X:
        replace Y in P by (Y intersect X) and Y \ X
        for every symbol x:
            if (Y, x) in W:
                replace (Y, x) in W by (Y intersect X, x) and (Y \ X, x)
            else
                add either (Y intersect X, x) or (Y \ X, x) to W
return P

Note that there are two sources of non-determinism in this algorithm: we can remove an arbitrary element from W, and if (Y, x) is not in W then we have a choice as to whether to add (Y intersect X, x) or (Y \ X, x). Unless I have misunderstood something, the algorithm is supposed to be correct no matter what choices we make.

Now, here is my example:

The alphabet is {a, b, c} and the only accepting state is 4, so we start the algorithm with P = 0123|4 and W = {(4, a), (4, b), (4, c)}.

In the first round, suppose we choose (4, b) as our arbitrary element of W. Nothing moves to 4 on input b, so the inner loop is empty. We get back to the outer loop with P=0123|4 and W = {(4, a), (4, c)}.

Next, suppose we choose (4, c). Then X = 12, which intersects non-trivially with 0123, splitting it into 03|12. Since no (0123, x) belongs to W, the "if" condition always fails. Suppose that we add (12, a), (12, b) and (12, c) into W. We get back to the outer loop with P=03|12|4 and W = {(4, a), (12, a), (12, b), (12, c)}.

Next, suppose we choose (4, a). Then X = 3, which intersects non-trivially with 03, splitting it into 0|3. Since so (03, x) belongs to W, the "if" condition always fails. Suppose that we add (0, a), (0, b) and (0, c) into W. We get back to the outer loop with P=0|12|3|4 and W = {(12, a), (12, b), (12, c), (0, a), (0, b), (0, c)}.

All of the rest of the main loop iterations leave P alone, since 0 is the only state that leads into any of 0, 1, or 2. So we end up returning 0|12|3|4. This is clearly wrong, though, because the string "aa" is an accepting input for state 1 but not state 2, so states 1 and 2 are not equivalent.

Hopcroft's algorithm works well on complete DFA. (ie. for $M=\{Q,\Sigma,\delta,q_0,F\}$, the transition function $\delta:Q\times\Sigma\to Q$ is a total function).

For incomplete DFA with partial state transition function $\delta$. You can always convert it to complete DFA $M'=\{Q',\Sigma,\delta',q_0,F\}$ where $$Q'=Q\cup\{q_{err}\}$$ and $\delta'$ extends $\delta$ by define $\delta_a(q)=q_{err}$ for all undefined $\delta_a(q), \delta_a\in\delta,q\in Q\cup\{q_{err}\}$.


A multi-user, multi-processing operating system cannot be implemented on hardware that does not support A multi-user, multi-processing operating system cannot be implemented on hardware that does not support

Address translation
DMA for disk transfer
At least two modes of CPU execution (privileged and non-privileged)
Demand paging

My attempt:

Somewhere it explain as : Address translation is needed to provide memory protection so that a given process does not interfere with another.

We also need at least 2 modes of execution to ensure user processes share resources properly and OS maintains control. This is not required for a single user OS like early version of MS-DOS.

Demand paging and DMA enhances the performances- not a strict necessity.

    Can you explain it in a formal way, please?

None of the above.

As you noted, DMA and demand paging can be useful features but are not necessary to support multiple users and multiprocessing.

Address translation is not necessary even for memory protection. Memory protection can be separated from address translation via a protection lookaside buffer or memory protection unit.

Providing a distinct privileged operating mode in the processor is not necessary for a multiuser system. In theory, provable trust of software can provide protection against misuse by users. Another alternative is capability systems; one can use non-forgeable fat pointers to provide resource protection.


Is it possible for a stack-based programming language to be concurrent? I have been reading about stack-based programming languages, such as FORTH and Cat, and it seems that given their nature, they can only execute one action at a time regardless of their paradigm (FORTH is imperative whereas Cat is functional).

An imperative language would modify the stack, and a purely functional language, such as Joy, would return a new stack, but the point is that only one stack is used at a time.

So, can stack-based programming languages be concurrent? Could they achieve concurrency by using multiple stacks at the same time or something alike?

Is it possible to implement lazy evaluation in a stack-based programming language?

Please correct me if I am misunderstanding anything about the languages and concepts mentioned above

So, can stack-based programming languages be concurrent?

Sure.

  Could they achieve concurrency by using multiple stacks at the same time or something alike?

Already for normal languages multi-threading usually means having multiple "call" stacks. It would be completely natural to give each thread its own data stack. It would be straightforward to have an actor, say, whose body was implemented by code in a stack-based language. Explicit parallelism a la GHC's par annotations should be reasonably straightforward. The main issue with executing things in parallel is that you don't know what the stack effect of the code will be until you execute it. However, using a Joy-like syntax, one could imagine [a b c] par as executing a b c either against an empty stack or a copy of the stack and only keeping the top-most element of the stack on completion (or pushing some dummy value if the stack is empty). You could imagine variations. Implicit parallelism would be harder to do naively as compared to, say, a purely functional language, but certainly could be done as well. The compiled code of a user-defined combinator is often not too different from "normal" code.

  Is it possible to implement lazy evaluation in a stack-based programming language?

Unknown stack effects are again the tricky part. If you design the language such that all stack effects can be determined statically, then it doesn't seem too challenging. If you have laziness be explicit, then it also seems relatively straightforward and would look roughly like Joy's quotations and i. One language that calls itself a lazy concatenative language seems to do a mixture of both of the above approaches from what I can tell. I don't really see how an implicitly lazy concatenative language would work in the face of dynamic stack effects, at least not in any vaguely usable way, but that might just be a lack of imagination on my part.

Incidentally, it is not uncommon for stack-based languages to have multiple stacks, e.g. Forth has a data stack and a return stack upon which you can also place arbitrary data.


Given a permutation of 0..N-1, determine the index of that permutation in the lexicographic ordering of all permutations of 0..N-1, in linear time There are various $\mathcal O(n \log n)$ or worse solutions, but I'm looking for one that runs in $\mathcal O(n)$, or a proof that none exist.

The 2007 paper Linear-time ranking of permutations gives a linear time ranking algorithm for the lexicographic order, assuming arithmetic on numbers of length $O(n\log n)$ takes constant time.

The 2001 paper Ranking and unranking permutations in linear time presents a linear time ranking algorithm not requiring fast arithmetic on large numbers, but not for the lexicographic order. Regarding the latter, it states

  The whole problem of ranking permutations in lexicographic order seems inextricably intertwined with
  the problem of computing the number of inversions
  in a permutation, and it seems that a major breakthrough will be required to do that computation in linear time, if indeed it it possible at all.

On the other hand, it does mention an $O(n\log n/\log\log n)$ algorithm for ranking permutations in lexicographic order due to Dietz.


Is all data stored in computers stored as machine code? I know that the most basic (and least abstract) code for programming is machine code (with binary of 0s and 1s being the typical machine code).
I also know that computers can save data even if they are turned off, by different types of computer memory (storage device memory, RAM and other computer system devices which can "remember" some data).
Is all data stored in computers ("all data remembered in a given computer memory") stored as machine code?
Is what's saved in a computer's "memory" (and becoming actually effective by electrical current correctly distributed to the computer system) just binary machine code in the sense that if I could read and understand that data directly without an operating system interfacing it for me it should appear in my mind as machine code, or rather, is it something else?

I wouldn't put it that way.  What is stored in memory is bits.  It's just data in binary form.
Humans might then label some of those bits as "machine code" because we intend or expect it to be executed; or because it will be executed.  That's a matter of interpretation we apply.  The memory module just sees a bunch of bits.  It just sees some data and has no knowledge of what the meaning or intended purpose of that data will be.
Memory is not limited to storing executable code.  Computers also store other data in memory.  For instance, your computer might store a copy of an email, or a picture or photograph you took.  Those aren't code, but they can be stored in memory.
It may be helpful to think that the memory can be used to store data or can be used to store code -- but there is nothing in the computer architecture that enforces any distinction between the two.  From the perspective of the memory module, it is just bits.


Exact meaning of $2^{\mathcal{O}(f(n))}$ In Sipser's Introduction to the Theory of Computation he uses the notation $2^{\mathcal{O}(f(n))}$ to denote some asymptotic running time.

For example he says that the running time of a single-tape deterministic turing machine simulating a multi-tape non-deterministic turing machine is

$\mathcal{O}(t(n)b^{t(n)})=2^{\mathcal{O}(t(n))}$ where $b$ is the maximal number of options in the transtition function.

I was wondering if someone can clarify the exact definition of this for me:

My assumption is that if $g(n)=2^{\mathcal{O}(f(n))}$ then there exists $N \in \mathbb{Z}$ and $c \in \mathbb{R}$ s.t.

$g(n) \leq 2^{cf(n)}=(2^{f(n)})^c$ for all $n>N$.

Thank you

The class $O(f(n))$ consists of all functions $\phi$ such that for some $N,c > 0$, we have $\phi(n) \leq Cf(n)$ for all $n \geq N$.

The class $2^{O(f(n))}$ is simply
$$
2^{O(f(n))} = \{ 2^{\phi(n)} : \phi(n) = O(f(n)) \},
$$
which is essentially what you wrote.

A different way of looking at this is that $O(f(n))$ stands for some function $\phi(n)$ such that $\phi(n) \leq Cf(n)$ for all large enough $n$.

Given this point of view, $2^{O(f(n))}$ simply stands for some function of the form $2^{\phi(n)}$, where $\phi(n) = O(f(n))$.