Problem Detail: Borůvka’s algorithm is one of the standard algorithms for calculating the minimum spanning tree for a graph $G = (V,E)$, with $|V| = n, |E| = m$. The pseudo-code is: MST T = empty tree Begin with each vertex Read More …
Blog
[Solved]: What do f(x) and g(x) represent in Big O notation?
Problem Detail: I have been reading about Big O notation. People writing about Big O often use the terms $f(x)$ and $g(x)$. For instance, I often see people write things like $f(x) = O(g(x))$ or $f(x) in O(g(x))$. Obviously $f(x)$ is Read More …
[Solved]: Are all context-sensitive languages decidable?
Problem Detail: I was going through the Wikipedia definition of context-sensitive language and I found this: Each category of languages is a proper subset of the category directly above it. Any automaton and any grammar in each category has an equivalent Read More …
[Solved]: Data structures as algorithms themselves
Problem Detail: Can data structures be thought of as algorithms themselves? For example, I could implement a stack data structure that has certain non-functional characteristics. Is the separation between data structures and algorithms formally defined? Asked By : Ben Aston Answered By Read More …
[Solved]: Why are the two farthest points vertices of the Convex Hull?
Problem Detail: I read that in a 2D space, the two points farthest away must be in the convex hull (CH). Intuitively, I can see why. If the two farthest points are not in the convex hull, then there must be Read More …
[Solved]: Check whether it is possible to turn one BST into another using only right-rotations
Problem Detail: Given two binary search trees T1 and T2, if it is possible to obtain T2 from T1 using only right-rotation, we say that T1 can be right-converted to T2. For example, given three binary search tree T1, T2 and Read More …
[Solved]: Is log(n) in complexity class P?
Problem Detail: $log(n)$ is not polynomial; is a problem solvable in $mathcal{O}(log n)$ time in P? $ntimes log(n)$ is also not polynomial; is a problem solvable in $mathcal{O}(ntimes log n)$ time in P? If not, what complexity classes contain those problems? Read More …
[Solved]: Nested Big O-notation
Problem Detail: Let’s say I have a graph $|G|$ with $|E|=O(V^2)$ edges. I want to run BFS on $G$ which has a running time of $O(V+E)$. It feels natural to write that the running time on this graph would be $O(O(V^2)+V)$ Read More …
[Solved]: What does sublinear space mean for Turing machines?
Problem Detail: The problem of deciding whether an input is a palindrome or not has been proved to require $Omega(log n)$ space on a Turing machine. However, even storing the input takes space $n$ so doesn’t that mean that all Turing machines Read More …
[Solved]: Syntax of a Pushdown Automata transition function
Problem Detail: I just learned PDAs in class today, but am having problems understanding the syntax of the transition function. Could someone please explain to me the meaning of this syntax: $delta(q, lambda, S) = {(q, aaB), (q, bbA)}$ This is Read More …
