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

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

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

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

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

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

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

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

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 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 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 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 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 6 votes Guy E. Blelloch: Programming Parallel Algorithms Very clear introduction to parallel algorithms. View answer 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 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 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 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 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 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 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 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 ...