Problem Detail: Windows NT used a point-to-point protocol where a client can communicate “securely” with a server by using a stream cipher to encrypt an array of messages with some key $k$. The server also encrypts its response with the same Read More …
Blog
[Solved]: Modeling the problem of finding all stable sets of an argumentation framework as SAT
Problem Detail: As a continuation of my previous question i will try to explain my problem and how i am trying to convert my algorithm to a problem that can be expressed in a CNF form. Problem: Find all stable sets Read More …
[Solved]: Clarification on Tabu Search
Problem Detail: I need some help in understanding the ‘Tabu Search‘ Algorithm. (Wikipedia) I miss a simple explanation to Tabu Search. Anyway, I’m trying to refer to available resources and build an understanding. This is what I’m trying to ‘digest’: Tabu Read More …
[Solved]: Permuting natural numbers
Problem Detail: We have two integers $z, k$ We form a sequence now of first z natural numbers. i.e. $1, 2, 3, 4, ldots z$. Now we have to find total number of permutations of this sequence such that the sum Read More …
[Solved]: Hash function – uniformity / strong universality
Problem Detail: I am currently learning how randomised Hashing works. So, you have a class (aka family) $H$ of hash functions, each of which maps the universe $U$ to the hash table $N$. That class is called “strongly universal” or “pairwise Read More …
[Solved]: What is the algorithm for Shannon-Fano code? am I correct?
Problem Detail: I am wondering what is the true algorithm for the Shannon-Fano code? The the result I am getting based on the Algorithm in Wikipedia page contradicts the supposed/expected length of the produced code. According to the proof of Kraft’s Read More …
[Solved]: Order-preserving update of a sublist of a list of mutable objects in sublinear time
Problem Detail: Description Say I have a source list like: [“a”,”b”,”c”,”d”] and want to run a capitalization filter so if I change, “b” to “B”, my derived list looks like [“B”]. Next, if I change my source list’s “d” to Read More …
[Solved]: What type of algorithms are faster with a quantum computer?
Problem Detail: I am a beginning CS student and I am learning algorithms. I heard that even with quantum computers, that general sorting algorithms can never have better than $nlog n$ time. However, I also know that factoring algorithms would be Read More …
[Solved]: Use closure properties to transform languages to $L := { a^nb^n : nin mathbb N }$
Problem Detail: For the purpose of proving that they are not regular, what closure properties can I use to transform the languages $L_a = { a^*cw mid w in {a,b }^* land |w|_a = |w|_b }$ and $L_b = {ab^{i_1}ab^{i_2}ldots ab^{i_n} Read More …
[Solved]: Proving that NPSPACE $subseteq$ EXPTIME
Problem Detail: I am following “Introduction to the theory of computation” by Sipser. My question is about relationship of different classes which is present in Chapter 8.2. The Class PSPACE. $P subseteq NP subseteq PSPACE = NPSPACE subseteq EXPTIME$ I am Read More …
