Problem Detail: Let $G=(V,E)$ be a DAG. A subset $A subseteq V$ is called a kernel if for all $u,v in A$ $uv notin E$ and for all $v in V-A$ there exists an $a in A$ such that $av in Read More …
Author: ignougroup
[Solved]: Combinational Logic Circuits and Theory of Computation
Problem Detail: I’m trying to link Combinational Logic Circuits ( computers based on logical gates only ) with everything I have learned recently in Theory of Computation. I was wondering whether combinational logic circuits can implement computations in the same way Read More …
[Solved]: Computational complexity of the clique problem
Problem Detail: What is the best known approximation for the computational complexity of the clique problem? Is it accurate to consider it $O(2^n)$? Asked By : loveToCode Answered By : AJed Wikipedia is usually a good starting reference to well-known problems as the Read More …
[Solved]: How to improve my these specific math skills?
Problem Detail: I am student of CS. Problem is, I feel that I don’t have enough math knowledge to solve mathematical problems. When some programming problems arises which needs some math skills to solve then despite of the fact that I Read More …
[Solved]: Are there hardware lock implementations without test-and-set or swap?
Problem Detail: Locks are usually implemented thru test-and-set and swap machine-level instructions. Are there other implementations that do not use these? Also, can we say that all hardware level solutions to the critical section problem can be categorized into just three, Read More …
[Solved]: The most efficient way of finding/storing neighbourhood info during octree creation
Problem Detail: Currently I have a program which at some point creates an octree and AFTER the creation loops through all the nodes, for every node (O(n2/2)) and thus finds the neighbours, by a brute-force box-box intersection check. Since that is Read More …
[Solved]: Travelling Salesman which can repeat cities
Problem Detail: In the TSP problem, we usually assume a complete graph. If we can only visit each city once, we need a complete graph to ensure that there will be a path from every city to every other city. This Read More …
[Solved]: Is there a TM that halts on all inputs but that property is not provable?
Problem Detail: Does there exist a Turing machine that halts on all inputs but that property is not provable for some reason? I am wondering if this question has been studied. Note, “unprovable” could mean a “limited” proof system (which Read More …
[Solved]: Prove or disprove whether L is regular
Problem Detail: Let $Sigma = {0,1}$. For every word $w in Sigma^*$, let $|w|_0$ and $|w|_1$ denote the count of 0’s and 1’s, respectively, in $w$. Let $L$ be the language $$L = { w in Sigma^* mid |w|_0 gt |w|_1 Read More …
[Solved]: Is this phrase structure grammar from my textbook correct?
Problem Detail: I just started reading “Parsing Techniques, A Practical Guide”, Second Edition, by Dick Grune and Ceriel J.H. Jacobs. On page 12, the authors start describing a set of rules that can be used to generate the set of all Read More …
