Computer Science Weekly Newsletter

Computer Science newsletter

Top new questions this week:

Why is a quantum computer not capable of solving more problems than a classical computer?

On the Wikipedia page for quantum algorithm I read that [a]ll problems which can be solved on a quantum computer can be solved on a classical computer. In particular, problems which are ...

computability computation-models quantum-computing simulation  
asked by Erwin Rooijakkers 11 votes
answered by David Richerby 18 votes

When is the concatenation of two regular languages unambiguous?

Given languages $A$ and $B$, let's say that their concatenation $AB$ is unambiguous if for all words $w \in AB$, there is exactly one decomposition $w = ab$ with $a \in A$ and $b \in B$, and ambiguous ...

algorithms formal-languages computability regular-languages ambiguity  
asked by rstern 10 votes
answered by Yuval Filmus 9 votes

Could the Halting Problem be "resolved" by escaping to a higher-level description of computation?

I've recently heard an interesting analogy which states that Turing's proof of the undecidability of the halting problem is very similar to Russell's barber paradox. So I got to wonder: ...

computability turing-machines computation-models halting-problem  
asked by H2CO3 9 votes
answered by babou 14 votes

Kleene star operation on the empty language

In my text book it is mentioned that: $\emptyset^*=\{\epsilon\}$ where $\emptyset$ is an empty language. However, we know that $L \cdot \emptyset = \emptyset$, where $L$ is any Language. I am not ...

formal-languages kleene-star  
asked by Sagnik 8 votes
answered by babou 9 votes

What are the simplest examples of programs that we do not know whether they terminate?

The halting problem states there is no algorithm that will determine if a given program halts. As a consequence, there should be programs about which we can not tell whether they terminate or not. ...

asked by srvm 8 votes
answered by avsmal 17 votes

Data General MV/8000 virtues of "No mode bit"

I'm reading Tracy Kidder's "The Soul of a New Machine" where a team at Data General design a new machine (codenamed "Eagle", later named MV/8000). It is 32-bit extension of a previous architecture ...

asked by Morty 6 votes
answered by Wandering Logic 5 votes

Can an Earley Parser be made into a fuzzy parser similar to the Levenshtein Automata Algo for DFA?

There's a way to perform fuzzy parsing (accepts strings even with typos to a certain edit distance), with a DFA and a run-time constructed Levenshtein Automata of the input word. Can something ...

algorithms context-free finite-automata parsers string-metrics  
asked by Enjoys Math 6 votes
answered by babou 6 votes

Greatest hits from previous weeks:

What's the difference between a binary search tree and a binary heap?

These two seem very similar and have almost an identical structure. What's the difference? What are the runtime complexities of each?

data-structures binary-trees heaps  
asked by piperchester 17 votes
answered by ali786 13 votes

Why is quicksort better than other sorting algorithms in practice?

In a standard algorithms course we are taught that quicksort is $O(n \log n)$ on average and $O(n^2)$ in the worst case. At the same time, other sorting algorithms are studied which are $O(n \log n)$ ...

algorithms sorting  
asked by Janoma 135 votes
answered by Sebastian 104 votes

Can you answer these?

Complexity of cubic graph decomposition

I am aware that deciding the existence of decomposition of a cubic graph into edge disjoint claws is polynomial time solvable. What is the complexity of deciding the existence of decomposition of ...

complexity-theory graph-theory  
asked by Mohammad Al-Turkistany 2 votes

How does one calculate the block-sensitivity of a function?

I am looking at this paper : But somehow I am not being able to fish out a method to calculate this quantity called the "block-sensitivity". Can someone kindly ...

complexity-theory computability turing-machines boolean-algebra  
asked by user6818 1 vote

Does this data structure already exist, and is there a better alternative?

Consider a polymorphic Haskell function type, like the type for .: (a -> b) -> (b -> c) -> a -> c This type can be represented as a binary tree, in which every leaf is labeled, and ...

data-structures binary-trees functional-programming  
asked by Adam R. Nelson 4 votes
Subscribe to more Stack Exchange newsletters

Unsubscribe from this newsletter or change your email preferences by visiting your subscriptions page on

Questions? Comments? Let us know on our feedback site. If you no longer want to receive mail from Stack Exchange, unsubscribe from all emails.

Stack Exchange, Inc. 110 William St, 28th Floor, NY NY 10038 <3