Problem Detail: According to a book I am reading, the unary representation of a number exponentially larger than a base k representation of it. I, however, feel that the unary representation should scale linearly with the input. After all, 1 is Read More …
Category: Uncategorized
[Solved]: Is star closure of reverse of language equivalent to reverse of closure of that language
Problem Detail: is the following true $ (L^R)^* = (L^*)^R $ I tried the following to prove it true. let u,v belong to L then $ L^* = { u,v, uu, vv, uv, vu … } $ and $ (L^*)^R = Read More …
[Solved]: Proving that language is regular or not regular
Problem Detail: Let $L$ be a regular language. Prove that: $L_{+–}=left{w: exists_u |u|=2|w| wedge wuin Lright}$ $L_{++-}=left{w: exists_u 2|u|=|w| wedge wuin L right}$ $L_{-+-}=left{w:exists_{u,v} |u|=|w|=|v| wedge uwvin Lright}$ are regular and: $L_{+-+}=left{ uv:exists_w |u|=|w|=|v| wedge uwvin L right}$ is not Read More …
[Solved]: Does the write through cache copies the whole block or just the byte which is updated?
Problem Detail: Just a basic question to ask Does the write through cache copies the whole block or just the byte which is updated? I went through the following question Array A contains 256 elements of 4 bytes each. Its first Read More …
[Solved]: compressing a set of binary strings with fixed length
Problem Detail: I’m looking for a data structure / algorithm to store an unordered set S of binary strings of a fixed length n (i.e. all matching the following regular expression: [01]{n}). Insertion and lookup (“Is element x in the S?”) Read More …
[Solved]: Dynamic programming to find the least possible balance of a full binary tree
Problem Detail: I am given $n$ positive integers $x_1,x_2,cdots,x_n$ as input. These are the weights of the leaves in a full binary tree, $x_1$ being the leftmost leaf and $x_n$ the rightmost leaf. The weight of an internal node $v$ is Read More …
[Solved]: Good introduction to Turing’s work and complexity theory?
Problem Detail: I’m currently an undergrad whose been amazed by what Turing has done for the world. I know there are plenty of other amazing individuals, but Turing’s work specifically has always sounded the most interesting to me and I’m finally Read More …
[Solved]: Compression type that can be searched
Problem Detail: Is there ANY compression type that can compress a file, and then that compressed file can be searched without uncompressing the file? Asked By : Albert Renshaw Answered By : KWillets Compressed self-indexes such as the FM Index allow arbitrary substring Read More …
[Solved]: Weak hashing function for memorable IPv6 addresses
Problem Detail: IPv6 addresses in the form of 862A:7373:3386:BF1F:8D77:D3D2:220F:D7E0 are much harder to memorize or even transcribe than the 4 octets of IPv4. There have been attempts to mitigate this, making IPv6 addresses somehow more memorable. Is there an intentionally-weak hashing Read More …
[Solved]: An example of a non-regular grammar for a regular language?
Problem Detail: I understand that a regular language can be specified by either regular or non-regular grammars. What is an example of a non-regular grammar for a regular language? Asked By : espertus Answered By : atulgangwar Regular Language L = {aab} Non-regular Read More …
