Problem Detail: It’s easy to see how a multi-track Turing machine can simulate a single-track Turing machine; it does so by ignoring all but the first track. But how does it work the other way? I need a specification of a Read More …
Blog
Converting to CFG from a CFL?
Problem Detail: I am trying to learn CFG. Now to make a CFG from a CFL it is really difficult for me. Is there any simple rule or steps so that I can easily find a CFG for a CFL. I Read More …
Looking for a dictionary of math/CS notation
Problem Detail: There is an at-times dizzying array of symbols used in math and CS papers. Yet many assume basic familiarity that seems rarely taught in one place. I am looking for a dictionary something like the following, especially from a Read More …
How can I prove algorithm correctness?
Problem Detail: How can I prove algorithm correctness ? when i face a problem and come up with a solution the only way to know if this a valid solution or not is by trying some test cases. if they pass Read More …
Problem A is polynomially reducible to problem B…what can we say about A and B?
Problem Detail: This is a question on a practice final. Problem A is polynomially reducible to problem B. Which of the following statements is correct? I. If problem A is solvable in a polynomial time then problem B is solvable in Read More …
Is there C++ code that takes infinite time to compile?
Problem Detail: Is C++ as a formal language recursively enumerable? If yes, is there any invalid C++ code that takes “infinite” time to compile? Asked By : sai_preet Answered By : Bartosz Przybylski In theory this code should compile infinitely template<long long K> Read More …
How can one simulate a PDA with a FIFO queue PDA?
Problem Detail: I’m trying to figure out how a pushdown automata (PDA), which we know uses a stack (LIFO) can be simulated by a queue (FIFO). I understand that in a regular PDA, we only have access to the top most Read More …
When does the nearest neighbor heuristic fail for the Traveling Salesperson?
Problem Detail: Can you provide an example of NN algorithm failure on the Euclidean traveling salesman problem? I was trying to construct a specific example of this for my friends and was failing. Asked By : dylan Answered By : Karolis Juodelė Consider Read More …
Negative numbers in Subset-Sum
Problem Detail: If I have a set $A$ with positive and negative numbers, and a number to find C. It is possible to reduce the problem to one with only positive numbers in set $A$? I mean, it is possible to Read More …
Data Structure for Representing a Math Expression
Problem Detail: I’m looking to improve my object-oriented design skills and I came across a problem which asked to design classes to represent a mathematical expression such as (a + b) * ( c – d / e) in memory so Read More …
