# 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

### 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

### 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

### 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

### 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. ...

turing-machines

### 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 ...

computer-architecture

### 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

## 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

### 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

## 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

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

I am looking at this paper : http://arxiv.org/pdf/1411.3419v1.pdf 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