Question Detail: People often say that LR(k) parsers are more powerful than LL(k) parsers. These statements are vague most of the time; in particular, should we compare the classes for a fixed $k$ or the union over all $k$? So how Read More …
Blog
Why would anyone want CISC?
Question Detail: 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 Read More …
Proof that a randomly built binary search tree has logarithmic height
Question Detail: How do you prove that the expected height of a randomly built binary search tree with $n$ nodes is $O(log n)$? There is a proof in CLRS Introduction to Algorithms (chapter 12.4), but I don’t understand it. Asked By Read More …
Where are back edges in a DFS tree?
Question Detail: As I understand it when doing a DFS run when every new node is discovered and edge is added to the DFS tree from the parent of the new node to the new node. If that’s the case how Read More …
Are Turing machines more powerful than pushdown automata?
Question Detail: I’ve came up with a result while reading some automata books, that Turing machines appear to be more powerful than pushdown automata. Since the tape of a Turing machine can always be made to behave like a stack, it’d Read More …
Proving DOUBLE-SAT is NP-complete
Question Detail: The well known SAT problem is defined here for reference sake. The DOUBLE-SAT problem is defined as $qquad mathsf{DOUBLEtext{-}SAT} = {langlephirangle mid phi text{ has at least two satisfying assignments}}$ How do we prove it to be NP-complete? More Read More …
Why has research on genetic algorithms slowed?
Question Detail: While discussing some intro level topics today, including the use of genetic algorithms; I was told that research has really slowed in this field. The reason given was that most people are focusing on machine learning and data mining. Read More …
Every simple undirected graph with more than $(n-1)(n-2)/2$ edges is connected
Question Detail: If a graph with $n$ vertices has more than $frac{(n-1)(n-2)}{2}$ edges then it is connected. I am a bit confused about this question, since I can always prove that for a graph to connected you need more than $|E|>n-1$ Read More …
How to construct and write down a Turing machine for a given language?
Question Detail: In my class we just started learning about Turing machines. I think I understand the concept but am unsure how to syntactically solve any problem related to one. I am presented with the problem: Build a Turing machine accepting Read More …
Designing a DFA that accepts strings such that nth character from last satisfies condition
Question Detail: This is a homework question, so I am only looking for hints. I got a question in an assignment which states : Design a DFA that accepts strings having 1 as the 4th character from the end, on the Read More …
