Raphael
  • Member for 11 years, 4 months
  • Last seen more than a month ago
Are there non-constructive algorithm existence proofs?
Accepted answer
37 votes

Consider the function (taken from here) $\qquad \displaystyle f(n) = \begin{cases} 1 & 0^n \text{ occurs in the decimal representation of } \pi \\ 0 & \text{else}\end{cases}$ Despite the ...

View answer
Are runtime bounds in P decidable? (answer: no)
31 votes

This is a rephrasing of Emanuele Viola's answer with the goal to be more understandable. We show that the given problem $P$ is undecidable by reducing the general halting problem $H$ to it. Let $(M, ...

View answer
What kind of mathematical background is needed for complexity theory?
26 votes

Apart from basic stuff, probably: Combinatorics -- You might find youself counting things quite regularly Stochastics -- For average case analyses and randomized algorithms I like Concrete ...

View answer
For a language to be programmable, is it mandatory that it be based on a context free grammar
Accepted answer
22 votes

Two times no. First, most HPLs are not context free. While they usually have syntax based on a CFG, they also have what people call static semantics (which is also often included in the term syntax). ...

View answer
What tools do you use to write papers?
22 votes

In addition to what others say, I like the package todonotes for LaTeX that allows to have colorful reminders of what remains to do in the text.

View answer
Is the Chomsky-hierarchy outdated?
20 votes

If you consider Chomsky's Hierarchy with "modern" names (i.e. REG, LIN, CFL, CSL, RE resp. DFA/NFA, PDA, LBA, TM), I say: No, it is not outdated! Reason 0: It is still correct in the sense that its ...

View answer
Counting words accepted by a regular grammar
20 votes

Let $A = (Q = \{q_1, \dots, q_n\}, \Sigma, \delta, Q_F)$ be a (nondeterministic) finite automation with starting state $q_1$, $Q_F \subseteq Q$ and $\delta \subseteq Q\times\Sigma\times Q$. Let $Q_i(...

View answer
For which problems in P is it easier to verify the result than to find it?
18 votes

Deciding if a value exists in an array takes time $\Omega(n)$ (or $\Omega(\log n)$ if the array is sorted). Verifying that an array contains the given value at a given position is possible in time $...

View answer
Why naturals instead of integers?
18 votes

There exists a computable bijection between $\mathbb{N}$ and $\mathbb{Z}$. Therefore it is sufficient to reason about computability and the like only using natural numbers, all the time knowing that ...

View answer
Are there any counterintuitive results in theoretical computer science?
18 votes

Computability certainly screws most students. A beautiful example with high confusion rate is this: $f(n) := \begin{cases}1, \quad \pi \text{ has } 0^n \text{ in its decimals} \\\\ 0, \quad else\end{...

View answer
Known algorithms to go from a DFA to a regular expression
14 votes

By far the nicest procedure I have seen is the one mentioned by Sylvain. In particular, it seems to yield more concise expressions than others. I wrote this document explaining the method for ...

View answer
(False?) proof for computability of a function?
14 votes

I think -- and hope -- that every computer science student is confronted with this problem which feels like a paradoxon. It is a very good example for the difference of computable in TCS sense and ...

View answer
What are regular expressions good for?
13 votes

Some examples of regular languages with practical importance: (reasonable) email adresses (see comments for caveats) (well-formed) URLs (or even URI in general) the set of valid identifiers in any ...

View answer
What is mathematical difference between "random" and "unique"?
Accepted answer
12 votes

When you say random numbers you want to have a series of numbers such that given any sequence of $i-1$ numbers, the probability of the $i$th number having a certain value is independent from all its ...

View answer
Collaborative tools for dummies/professors
Accepted answer
12 votes

First off: If your are interested in real-time collaborative editing, try something like gobby. It lets you literally edit a document at the same time. As for revision systems, I am only familiar ...

View answer
Encoding of binary trees as a regular language?
9 votes

As Peter Shor mentions in a comment, the number of full binary trees with $n+1$ leaves is given by the $n$-th Catalan number $C_n$. It is known that the Catalan numbers have generating function $C(x) ...

View answer
Examples of the price of abstraction?
9 votes

Many interesting problems that nature sciences come up with turn out to be NP-hard in the classical sense. While this notion is theoretically perfectly valid it does not help the biologist or ...

View answer
References for TCS proof techniques
7 votes

We have been starting some reference questions on cs.SE covering typical (so far introductory) TCS problems. Besides general relevance, some answers contain methods that may not be known to every ...

View answer
Hardness jumps in computational complexity?
6 votes

I just read a paper that deals with hypergraph partitioning. The Problem is defined as this, quote: Given two parameters $k$ and $l$, $1 \leq l < k$, the problem [$P^l_k$] is defined as follows: ...

View answer
Removing recursion - a look into theory behind the scenes
Accepted answer
6 votes

If I understand correctly, you are clear about converting functions that contain no other function calls but to themselves. So assume we have a "call chain" $F \to F_1 \to \dots \to F_n \to F$. If we ...

View answer
What papers should everyone read?
6 votes

Guy E. Blelloch: Programming Parallel Algorithms Very clear introduction to parallel algorithms.

View answer
How does Theoretical Computer Science relate to security?
6 votes

Theorem provers have been used to some extent for proving correctness of software, hardware and protocols. See, for example, here or here. The problem of data flowing in undesired ways through ...

View answer
Relationship between context-free/decidable languages and NP
5 votes

Basic Facts: CYK-algorithm parses inputs of length $n$ for any CFG in Chomsky normal form in time in $\mathcal{O}(n^3)$ Every CFL is generated by a CFG in Chomsky normal form Every regular language ...

View answer
Was the reason that Computers were invented to solve a philosophical question about the foundations of mathematics?
5 votes

In 1936, Konrad Zuse developed what was for all intents and purposes the Z1 the first computer in the modern sense. This fact is little known but has since been acknowledged even by his international ...

View answer
How practical is Automata Theory?
5 votes

Thrown together with logics, automata can offer ways to check statemens like $\qquad A \models \varphi$ for an automaton $A$ and a formula $\varphi$. If $A$ is a model of a system and $\varphi$ a ...

View answer
What tools do you use to give presentations?
5 votes

Especially in TCS/maths, the good old blackboard can be of good use for proofs and examples. If there is none available or you have to project or record, try software implementations such as ...

View answer
Models of random graphs, for real computer networks
5 votes

Instead of laboriously finding, justifying and analysing a specific model, you might want to use what real life data you have (if you have any). That means defining a generic probabilistic model and ...

View answer
Dinner-table description of theoretical computer science?
5 votes

The posed question is really a hard one since most people have no idea what computer scientists in general do. This is very different from other disciplines. I like to use the following analogy: (T)...

View answer
Which definition of asymptotic growth-rate should we teach?
5 votes

When I took basic courses, we were given the $\exists c,n_0 \dots$ thing as definition and the other stuff as theorem. I think the first one is more natural for many people that think discrete rather ...

View answer
What's a good news source for Computer Science?
4 votes

If you want to follow a specific field, try arxiv.org.

View answer