Problem Detail: I bought a great puzzle called Icosoku. Wikipedia describes it as: “The puzzle frame is a blue plastic icosahedron, and the pieces are 20 white equilateral-triangular snap-in tiles with black dots and 12 yellow pins for the corners. The Read More …
Blog
[Solved]: Updating the MST of a graph G = (V,E) when decreasing the weight of one of the edges that is not part of the MST
Problem Detail: You are given a weighted undirected graph G = (V,E). You have run Prim’s algorithm and found the MST of this graph. Now you pick one edge that is not part of the MST and reduce its weight by Read More …
[Solved]: How to represent whitespace in a context-free grammar?
Problem Detail: Say we want to support: xx The following grammar does accept it: S -> xAx A -> ε. because S => xAx => xx. But what about supporting: x x I realize this might be a stupid question but Read More …
[Solved]: Is there a binary tree structure with fast access to recently accessed elements and worst $O left( log n right )$ complexity?
Problem Detail: The idea of splay trees is very nice as they move frequently accessed elements to the top, which can gain a considerable speed up in many applications. The drawback is that in the worst case an operation can have Read More …
[Solved]: Eliminating useless productions resulting from PDA to CFG converison
Problem Detail: In my class we used a Pushdown Automata to Context Free Grammar conversion algorithm that produces a lot extraneous states. For example, for two transitions, I am getting the following productions $$begin{gather*} delta(q_0,1,Z) = (q_0,XZ) {}[q_0,Z,q_0] to 1[q_0,X,q_0][q_0,Z,q_0] {}[q_0,Z,q_0] Read More …
[Solved]: Why does the square root of n! grow exponentially faster than exponential functions?
Problem Detail: I am going through Normal Subgroup Reconstruction and Quantum Computation Using Group Representations by Hallgren et al. In the proof of the theorem $6$ of the paper on page 632, the authors go on proving the difference between the Read More …
[Solved]: What exactly is computation?
Problem Detail: I know what computation is in some vague sense (it is the thing computers do), but I would like a more rigorous definition. Dictionary.com’s definitions of computation, computing, calculate, and compute are circular, so it doesn’t help. Wikipedia defines Read More …
[Solved]: If L1 ∪ L2 and L1 are regular, is L2 also regular?
Problem Detail: This is a problem in a theory of computation book that’s stumping me: Suppose that we know that $L_1 ∪ L_2$ and $L_1$ are regular. Can we conclude that $L_2$ is regular? Explain. At first, I thought I could Read More …
[Solved]: Matrix Max in less than O(n)
Problem Detail: I am attempting to find the maximum value in a matrix (or 2d array) and want to find it in less than O(n) time. The easiest way, which results in O(n) run time, is an element wise search. If Read More …
[Solved]: XOR-like behavior in flow networks
Problem Detail: XOR is not the correct name, but I am looking for some kind of exclusive behavior. I am currently solving a set of different (assignment) problems by modeling flow networks and running a min-cost-max-flow algorithm. Flow networks are quite Read More …
