Problem Detail: This language I think is not accepted by a deterministic one counter but accepted by a non-deterministic one counter : $L = {a^{i}b^{j}c^{k} mid (i=j) vee (j=k) text{ such that } igeq0, jgeq0, kgeq0}$ But how to prove this Read More …
Blog
[Solved]: Definition of $Theta$ for negative functions
Problem Detail: I’m working out of the 3rd edition CLRS Algorithms textbook and in Chapter 3 a discussion begins about asymptotic notation which starts with $Theta$ notation. I understood the beginning definition of: $$Theta(g(n)) = { f(n),|, exists, c_1, c_2 > Read More …
[Solved]: Use minimum number of swaps so each bin contains balls of the same color
Problem Detail: There are $n$ bins, the $i$th bin contain $a_i$ balls. The balls has $n$ colors, there are $a_i$ balls of color $i$. Let $m=sum_{i=1}^n a_i$. A swap is take a ball from one bin and swap with a ball Read More …
[Solved]: Counting solutions to system of linear equations modulo prime
Problem Detail: I have implemented Gaussian elimination for solving system of linear equations in the field of modulo prime remainders. If there is a pivot equal to zero I assume the system has no solution but how to calculate number of Read More …
[Solved]: Partial order, total order, and version order in transaction histories
Problem Detail: In Section 3.1.2 “Transaction Histories” of the PhD thesis by Atul Adya [1]: A history $H$ over a set of transactions consists of two parts: (1) a partial order of events $E$ that reflects the operations (e.g., read, write, Read More …
[Solved]: Does a DFA accept an empty string if $q_0$ is the accept state?
Problem Detail: Suppose $q_0$ is the start state, does this mean that if it’s the accept state, then the machine must accept the empty string since it cannot have a transition with the empty string? Asked By : maregor Answered By : David Read More …
[Solved]: Why Turing wasn’t wrong?
Problem Detail: Computer science is a science and as a science each thesis can be refutable. So, why there is no “major” counter-thesis? After all, Einstein was a well known “genius” and has lived a long life and he has got Read More …
[Solved]: How to prove that 3-coloring is decidable?
Problem Detail: In order to prove that 3-coloring is decidable, is it sufficient to say: Each node in the graph has 3 possible colors Therefore we can enumerate over all $3^n$ possibilities and then check that no two edges connect nodes Read More …
[Solved]: Why is it seemingly easier to resume torrent downloads than browser downloads?
Problem Detail: I really wonder how torrent downloads can be resumed at later point of time. If such a technology exists, then why is it not possible in browsers? It is often not possible to pause a browser download so that Read More …
[Solved]: anonymous lambda functions (functional programming)
Problem Detail: What are anonymous (lambda) functions? What is the formal definition of an anonymous function in a functional programming language? In my simple terms, when I am programming in scheme/lisp I would say an anonymous (lambda) function is a function Read More …
