We learned about the class of context-free languages $\mathrm{CFL}$. It is characterised by both context-free grammars and pushdown automata so it is easy to show that a given language is context-free. How do I show the opposite, though? My TA has been adamant that in order to do so, we would ha...

We learned about the concept of enumerations of functions. In practice, they correspond to programming languages. In a passing remark, the professor mentioned that the class of all total functions (i.e. the functions that always terminate for every input) is not enumerable. That would mean that ...

In our computer systems lecture we were introduced to the MIPS processor. It was (re)developed over the course of the term and has in fact been quite easy to understand. It uses a RISC design, that is its elementary commands are regularly encoded and there are only few of them in order to keep th...

When implementing a dictionary ('I want to look up customer data by their customer IDs'), the typical data structures used are hash tables and binary search trees. I know for instance that the C++ STL library implements dictionaries (they call them maps) using (balanced) binary search trees, and ...

I foresee a number of topics that will probably come up again and again on this site in the future. As one has already been asked, I think we may want to come up with a policy for these types of topics while we're still in beta. The topic in question is 'how to determine the running time of an a...

We have two tags at the moment which seem to be the same topic. I think we should make one the synonym for the other. So my suggestion is to merge formal-grammars into grammars.

When reporting algorithmic complexity of an algorithm, one assumes the underlying computations are performed on some abstract machine (e.g. RAM) that approximates a modern CPU. Such models allow us to report time and space complexity of algorithms. Now, with the spread out of GPGPUs, one wonders ...

It is arguable that most languages created to describe everyday problems are context-sensitives. In the other hand, it is possible and not hard to find some languages that are not recursive or even not recursively-enumerable. Between these two types are the recursive non-context-sensitive langua...

At the midterm there was a variant of the following question: For a decidable $L$ define $$\text{Pref}(L) = \{ x \mid \exists y \text{ s.t. } xy \in L\}$$ Show that $\text{Pref}(L)$ is not necessarily decidable. But if I choose $L=\Sigma^*$ then I think $\text{Pref}(L)$ is also $\Sigma^*...

Let $\cal{S}=\{S_i\}_{1\leq i\leq n}$ be a partial $(m,k)$-design and $f: \{0,1\}^m \to \{0,1\}$ be a Boolean function. The Nisan-Wigderson generator $G_f: \{0,1\}^l \to \{0,1\}^n$ is defined as follows: $$G_f(x) = (f(x|_{S_1}) , \ldots, f(x|_{S_n}) )$$ To compute the $i$th bit of $G_f$ we take...

Originally: http://math.stackexchange.com/questions/74453/how-is-the-loop-invarient-obtained-in-this-square-root-bound-finding-algorithm but unanswered Consider the following algorithm. u := 0 v := n+1; while ( (u + 1) is not equal to v) do x := (u + v) / 2; if ( x * x <= n) u :...

How do I prove that the Toffoli gate is universal?

Originally http://math.stackexchange.com/questions/22614/help-understand-texthandle-in-parsing-problem but unaswered there The BNF is defined as followed: S -> aAb | bBA A -> ab | aAB B -> bB | b The sentence is: aaAbBb And this is the parse tree: Phrases: aaAbBb, aAbB, bB Simp...

Re-posting from cstheory as suggested I'm a graduate student taking a course in theory of computation and I'm having serious trouble producing content once I'm asked to. I'm able to follow the textbook ( Introduction to the Theory of Computation by Michael Sipser ) and lectures; however when as...

When searching graphs, there are two easy algorithms: breadth-first and depth-first (Usually done by adding all adjactent graph nodes to a queue (breadth-first) or stack (depth-first)). Now, are there any advantages of one over another? The ones I could think of: If you expect your data to be...

Our professor asked us to think of a function in OCaml that has the type 'a -> 'b i.e. a function of one argument that could be anything, and that can return a different anything. I thought of raise, but the professor said there was a solution that doesn't require any function in the stand...

Accordint to this article $P \neq NP$ http://arxiv.org/ftp/arxiv/papers/1111/1111.0305.pdf But.. I know that is not a real demonstration. The idea is quite simple: a variation of TSP. What is the route (with weights included) with a lowest lexicographical order after the strings represen...

I remember coming across the following question about a language that's supposedly is context-free, but I was unable to find a proof of the fact. Have I perhaps misremembered the question? Anyway, here's the question: Show that the following language is context free $\{xy | |x| = |y| but x\n...

It was bound to happen and thankfully, it did now rather than later: we received the first question about a claim regarding P?=NP. Some topics, in particular this, attract lots of public attention and laymen research. I do not want to belittle such efforts, but according to experts (i.e. complex...

In Hromkovič's "Algorithmics for Hard Problems" (2nd edition) there is this theorem (2.3.3.3, page 117): There is a decision problem $P$ such that for every algorithm $A$ that solves $P$ there is another algorithm $A'$ that also solves $P$ and additionally fulfills $\qquad \forall^\inft...

I'm working on a parser for a C-style language, and for that parser I need the regular expression that matches C-style /**/ comments. Now, I've found this expression on the web: /\*((!\*)*\*+(!*|!/))*((!\*)*\*+|(!\*)*\*/ However, as you can see, this is a rather messy expression, and I have no...

I remember I didn't have this problem before, but now I refreshed the page trice but the LaTeX part isn't shown properly.

I was about to ask a question but the toolbar is gone and I cannot upload the image to post the question. It's not the case on other SE sites, not even in meta.CS.

I came across this figure, expressing that context-free and regular languages are subset of efficient problems. I perfectly understand that efficient problems are subset of undecidable problems because we can solve them but it could take a very long time. Why are all context-free and regular lan...

I was reading an article that described the switch between user-space and kernel-space that happens upon a system call. The article said An application expects the completion of the system call before resuming user-mode execution. Now, until now I was assuming that some system calls are bl...

This question related to writing titles and editing posts. It is well-understood that titles should be expressive and tell about the content of the post, i.e., about the specific question being asked. Along these lines, should we encourage having latex in the title, or ASCII (or, wording) approxi...

I am reading about atomicity and came across the following scenario int x = y = z = 0; Thread 1 Thread 2 --------- -------- x = y + z y = 1 z = 2 Which gives the following sets of output $$\begin{array}{ccc}1&2&3\\ T1 : x = y + z&T2 : y = 1&...

Is it not necessary to encode both the uppercase and lowercase letter while encoding a message with the move-to-front transform? From an old computer science course exam, the problem was to encode Matt_ate_the_mat starting with an empty list. Using the author's solution methodology of not taking...

Here is the standard pseudocode for breadth first search: { seen(x) is false for all x at this point } push(q, x0) seen(x0) := true while (!q.empty()) x := pop(q) visit(x) for each y reachable from x by one edge if not seen(y) push(q, y) seen(y) := true Here push and pop ...

Note: This is a seeding question and might have appeared on StackOverflow before. (Feel free to close if you think it is inappropriate). You are given an array of $2n$ elements $$a_1, a_2, \dots, a_n, b_1, b_2, \dots b_n$$ The task is to interleave the array, using an in-place algorithm such ...

In some other communities, there have been discussions about the use of the "Community wiki"-function. The policies seem to differ from site to site, so before it comes to any problems here about what should be CW'ed and what should be deleted: What is our stance? References: The Future of Co...

Suppose the datatype for a BST is defined as follows (in SML) datatype 'a bst_Tree = Empty | Node of (int * 'a) * 'a bst_Tree * 'a bst_Tree; So there are two cases one in which the BST is Empty or it can have a (key,value) as well as two children. Now, for the case of an AVL where the con...

I asked a question that has a tricky answer, which I saw explained in some dark corner of the Internet a long time ago. I did so after seeing another question that was posted by someone who knew the answer, just to seed the site with interesting content. The response, a highly voted comment "thi...