Problem Detail: A sink in a directed graph is a node with no outgoing edges. If I perform a depth first search, why is it that the node with the least post-order number (and thus the highest pre-order number) not necessarily Read More …
Blog
[Solved]: Category theory (not) for Programming?
Problem Detail: After learning Haskell and other not so pure FP languages I decided to read about Category theory. After gaining good understanding of Category theory I started thinking about how the concepts of category theory can be used to think Read More …
[Solved]: Is it possible to get Nth Fibonacci number in sublinear time?
Problem Detail: I was researching the topic of Fibonacci numbers and asymptotic complexity of generating them. Coming across a seemingly paradoxical conclusion, I’ve decided to check out if you agree with my explanation. The naive algorithms runs in $O(n)$, if we Read More …
[Solved]: How can an algorithm have exponential space complexity but polynomial time complexity?
Problem Detail: For enumerating the minimal feedback vertex sets of a graph Schwikowski and Speckenmeyer show an algorithm “GENERATE-MFVS” in their publication “On enumerating all minimal solutions of feedback problems“. It is said that it runs in polynomial time but uses Read More …
[Solved]: What does an input string of epsilon mean?
Problem Detail: I am currently reading Introduction to the Theory of Computation (Sipser), and after introducing epsilon labeled transition arrows, the book shows the following NFA: I was following it until I read the following : Practice with it to satisfy Read More …
[Solved]: If a point is a vertex of convex hull
Problem Detail: The exercise is Given a set of point $S$ and a point $p$. Decide in $O(n)$ time if $p$ is a vertex of convex polygon formed from points of $S$. The problem is I am a little bit confused Read More …
[Solved]: Classification of job shop scheduling problems
Problem Detail: I’m writing a program (using genetic algorithms) that finds sort-of-optimal scheduling plan for a factory. The factory has several types of machines (say, locksmith, miller, welding) There are few machines of each type. (say, 3 locksmiths, 2 millers, 3 Read More …
[Solved]: How to read out a double negation in propositional logic
Problem Detail: How would one verbally say ~~R where R = my program is correct? The tildes are negation symbols. I’m not sure if it just cancels out and comes out as ‘my program is correct’ or if it’s something else. Read More …
[Solved]: Returning a random subset with length k of N strings while only storing at most k of them
Problem Detail: Here’s the problem. I’ve written a program that reads strings from stdin, and returns a random subset of those strings. The only other argument provided to the program is the length of the subset, $k$. The subset must contain Read More …
[Solved]: How to decode multiple-digit gamma codes and get the gap sequence?
Problem Detail: How to decode gamma code ($gamma$ code): 1110001110101011111101101111011 and get the gap sequence? Detailed information about Gamma codes ($gamma$ codes) with a brief example of decoding can be found here. But in their example there is only one case Read More …
