Blog

Problem Detail: A question was asked at Stack Overflow (here): Given an integer $N$, print out all possible combinations of integer values of $A,B,C$ and $D$ which solve the equation $A^2+B^2+C^2+D^2 = N$. This question is of course related to Bachet’s Read More …

Problem Detail: This is a problem from a past contest at topcoder : Problem. Its solution is given here : Solution [Scroll Down to Penguin Emperor] I am unable to understand how the section with subheading “Combinations are associative” works. What Read More …

Problem Detail: Directly from Wikipedia, a set of vertices $X subseteq V(G)$ of a graph $G$ is independent if and only if its complement $V(G) setminus X$ is a vertex cover. Does this imply that the complement of the independent set Read More …

Problem Detail: I want to prove that any polynomial of degree $k$ is in $Theta(n^k)$. The coefficient of $n^k$, $a_{k}$, is positive. I know I need $0 leq c_{1}n^k leq a_{k}n^k + … + a_{0} leq c_{2}n^k$ for all $n geq Read More …

Problem Detail: If P does equal NP, will it still be possible do design a cryptosystem where the optimal cryptanalysis algorithm takes, say, the square of the time taken up by the legitimate encryption and decryption algorithms? Do any such algorithms Read More …

Problem Detail: Is there a data structure to keep a list of elements (not necessarily sorted) that performs the Access (by index) and Insert operations in a reasonable asymptotic time? When I say “reasonable time”, I mean that it should be Read More …

Problem Detail: The subset-sum problem is a classic NP-complete problem: Given a list of numbers $L$ and a target $k$, is there a subset of numbers from $L$ that sums to $k$? A student asked me if this variant of the Read More …

Problem Detail: How can we systematically convert a non-deterministic Turing machine into a deterministic Turing machine that recognizes the same language? Asked By : Kevin Answered By : Hendrik Jan The deterministic machine simulates all possible computations of a nondeterministic machine, basically in Read More …

Problem Detail:  Given a set $S$ of points $p_1,..,p_2$ give the most efficient algorithm for determining if any 3 points of the set are collinear. The problem is I started with general definition but I cannot continue to actually solving Read More …