Problem Detail: I try to understand balance factors change after local rotations in AVL trees. Given the rotate_left operation: x y’ / / a y => x’ c / / b c a b and $b(x)$, $b(y)$ – balance factors for Read More …
Blog
[Solved]: Construct a context-free grammar for a given set of words
Problem Detail: I have seen a few years back a nice and simple algorithm that, given a (finite) set of words in some alphabet, builds a context-free grammar for a language including these words and in some sense “natural” (e.g., the Read More …
[Solved]: Structure of a Pumping Lemma proof: contradiction or counterexample?
Problem Detail: This site is full of Pumping Lemma questions, and I do admit I’ve not read them all. I’ve tried some proofs myself and they seem to work, but I can’t find anywhere what is the (general) exact structure of Read More …
[Solved]: What’s the purpose of ANDing a bit mask with all bits set to a value?
Problem Detail: I’m adapting an algorithm for calculating a CRC 16-bit CCITT (XModem) value from an ASCII input. I’ve found some code here. I’m using the function the poster has in his question, but I’ve noticed at the bottom he does Read More …
[Solved]: If $L = L(M)$ then $L$ is a subset of $L(M)$ and $L(M)$ is a subset of $L$
Problem Detail: If $L = L(M)$ then $L$ is a subset of $L(M)$ and $L(M)$ is a subset of $L$. Can anyone clarify what does this mean? Asked By : makakas Answered By : Hendrik Jan This is just a set-theoretical equality. Two Read More …
[Solved]: Complexity of the Dijkstra algorithm
Problem Detail: I’m little confused by computing a time complexity for Dijkstra algorithm. It is said that the complexity is in $O(|V|^2)$ – Wikipedia – Dijkstra, which I understand. It’s because for each node, we could theoretically relax edges going to Read More …
[Solved]: Why doesn’t parallelism necessarily imply non-determinism?
Problem Detail: I’m a student reading a book on threads. And I got when I got to non-deterministic and parallel programs, I got a bit confused. I hope you can help me out. I understand the difference between concurrency and parallelism. Read More …
[Solved]: Given an analysis of an algorithm, can we get Big-O, Theta, and Omega from this analysis?
Problem Detail: If we are given an analysis of an algorithm to be, for example, $5n^3 + 100n^2 + 32n$, can we therefore say that $T(n) = O(n^3)$, and $T(n) = Theta(n^2)$, and $T(n) = Omega(n)$, and all of those be Read More …
[Solved]: How do GPUs compute sines?
Problem Detail: I’ve been wondering lately how GPUs compute sines and cosines, and Google hasn’t helped me finding a precise answer. Initially, I was thinking that in order to make the computations as fast as possible, the GPU would use some Read More …
[Solved]: Are nearly all natural numbers compressible?
Problem Detail: A simple counting argument shows most strings can’t be compressed to shorter strings. But, compression is usually defined using Kolmogorov complexity. A string is compressible if its Kolmogorov complexity is less than its length, $K(s) < |s|$. The Kolmogorov Read More …
