Problem Detail: Solving the recurrence relation $T(n) = 2T(lfloor n/2 rfloor) + n$. The book from which this example is, falsely claims that $T(n) = O(n)$ by guessing $T(n) leq cn$ and then arguing $qquad begin{align*} T(n) & leq 2(c lfloor Read More …
Category: Uncategorized
[Solved]: Filling Rows of a Matrix Subject to Conditions
Problem Detail: I’m seeking to write an algorithm which, given a value of N, will fill a matrix consisting of (N+1)(N+2)(N+3)/6 rows and 4 columns with the integers from 0, … , N, subject to the conditions that: The sum of Read More …
[Solved]: How should I design a hash table where all the keys are permutations?
Problem Detail: I need to create a hash table to store values for (possibly all) permutations of 123456789, which is exactly 362 880 keys. Given that I know how all the keys look up front, it seems I that there should Read More …
[Solved]: Lambda Calculus: How do evaluation contexts “work”
Problem Detail: In the pure lambda calculus, we have the inductively defined set of terms (the grammar): $$e::= x mid lambda x . e mid e_1 e_2$$ Under the call-by-value evaluation strategy, we have the inference rules for beta-reduction and rules Read More …
[Solved]: Micro-optimisation for edit distance computation: is it valid?
Problem Detail: On Wikipedia, an implementation for the bottom-up dynamic programming scheme for the edit distance is given. It does not follow the definition completely; inner cells are computed thus: if s[i] = t[j] then d[i, j] := d[i-1, j-1] // Read More …
[Solved]: How to deal with arrays during Hoare-style correctness proofs
Problem Detail: In the discussion around this question, Gilles mentions correctly that any correctness proof of an algorithm that uses arrays has to prove that there are no out-of-bounds array accesses; depending on the runtime model, this would cause a runtime Read More …
[Solved]: What is a lay explanation for universal search?
Problem Detail: I am reading a book on a computer science topic but lack some of the prerequisite background. Normally when I run into terms I don’t understand I simply look them up, but for Universal Search I simply haven’t been Read More …
[Solved]: Is the language of words containing equal number of 001 and 100 regular?
Problem Detail: I was wondering when languages which contained the same number of instances of two substrings would be regular. I know that the language containing equal number of 1s and 0s is not regular, but is a language such as Read More …
[Solved]: Is there a sometimes-efficient algorithm to solve #SAT?
Problem Detail: Let $B$ be a boolean formula consisting of the usual AND, OR, and NOT operators and some variables. I would like to count the number of satisfying assignments for $B$. That is, I want to find the number of Read More …
[Solved]: Are there other ways to describe formal languages other than grammars?
Problem Detail: I’m looking for mathematical theories that deal with describing formal languages (set of strings) in general and not just grammar hierarchies. Asked By : mtanti Answered By : Raphael There are plenty of possibilities. Others have already mentioned automata which offer Read More …
