Problem Detail: Let a binary counter with the operations INCREMENT and DECREMENT. I need to show that you can’t implement this kind of counter with constant amortized time per operation. Hence, I need to show that there’s a series of $N$ Read More …
Author: ignougroup
[Solved]: Bankers algorithm – How does it work?
Problem Detail: I’m currently studying deadlocks and I’m trying to learn myself the bankers algorithm. In this example my teacher goes to B first, then C and finally A. He adds (I think) 2 (row b, Has) with 3 (free) and Read More …
[Solved]: How good are current AI researchers at simulating complex, first-person emotional states?
Problem Detail: I just read that IBM’s Watson would have a hard time answering questions like “tell me about your first kiss.” If you asked a modern, state-of-the-art chatbot questions like “tell me about a song that means a lot to Read More …
[Solved]: Solving the recurrence relation $T(n) = 2T(lfloor n/2 rfloor) + n$
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 …
[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 …
