Problem Detail: I am new to artificial intelligence. I have been trying to analyse the time complexity of 8-queen, by placing one by one without attack. One approach to achieve goal state is to “add a queen to any square in Read More …
Blog
[Solved]: Why is the reduction from Vertex-Cover to Subset-Sum of polynomial time?
Problem Detail: In the standard proof why Subset-Sum is (weakly) NP-complete, one reduces Vertex Cover to Subset-Sum by using suitable numbers with O(m+n) bits (where m is the number of edges and n the number of vertices). But how can we Read More …
[Solved]: Is there a flaw in this Wikipedia proof of cycle property of Minimum Spanning Tree?
Problem Detail: On wikipedia, there is a proof for the cycle property of the Minimum Spanning Tree as follows: Cycle Property: For any cycle C in the graph, if the weight of an edge e of C is larger than the Read More …
[Solved]: What is Simultaneous Multithreading
Problem Detail: I come from an electronics background. I know that there are three types of implementations of multithreading (see Computer Architecture: A Quantitative Approach, 5th Edition): Fine-grain multithreading issues instructions for different threads after every cycle. Coarse-grain multithreading only switches Read More …
[Solved]: How does ‘deforestation’ remove ‘trees’ from a program?
Problem Detail: I think understand how deforestation consumes and produces a list at the same time (from a fold and an unfold function — see this good answer on CodeReview here), but when I compared that with the wikipedia entry on Read More …
[Solved]: Why does the state remain unchanged in the small-step operational semantics of a while loop?
Problem Detail: Usually I see that in the structural operational semantics representation for the while loop, the program state don’t change: $(while > B > do >S, sigma) rightarrow (if >B > then >S; (while > B > do >S) > Read More …
[Solved]: Does the DFS algorithm differentiate between an ancestor and a parent while computing back edges?
Problem Detail: Below is the general code for DFS with logic for marking back edges and tree edges. My doubt is that back edges from a vertex go back and point to an ancestor and those which point to the parent Read More …
[Solved]: Generating inputs for random-testing graph algorithms?
Problem Detail: When testing algorithms, a common approach is random testing: generate a significant number of inputs according to some distribution (usually uniform), run the algorithm on them and verify correctness. Modern testing frameworks can generate inputs automatically given the algorithms Read More …
[Solved]: Undecidability of telling if a program returns true or false
Problem Detail: Consider the problem of taking an input Turing machine and determining if the final cell is a $0$ or $1$ after computation halts. On cases where it writes something else or does not halt, you are allowed to give Read More …
[Solved]: Linear-time algorithm to find an odd-length cycle in a directed graph
Problem Detail: Problem: Give a linear-time algorithm to find an odd-length (directed) cycle in a directed graph. (Exercise 3.21 of Algorithms by S. Dasgupta, C. Papadimitriou, and U. Vazirani.) The related [email protected] asks for the existence of an odd-length directed Read More …
