Problem Detail: If an algorithm runs in exponential time with exponential input then we say it runs in polynomial time ? Why ? Doesn’t the algorithm run in exponential time anyway ? How the input size affects ? Thanks. Asked By Read More …
Author: ignougroup
[Solved]: Detect if a sentence is in passive voice
Problem Detail: Given an English sentence, I am looking for a programmatic way to tell whether the sentence is written in passive voice. Currently, I just check if there is a was or were inside the sentence. If yes, then the Read More …
[Solved]: Proving closure under complementation of languages accepted by min-heap automata
Problem Detail: This is a follow-up question of this one. In a previous question about exotic state machines, Alex ten Brink and Raphael addressed the computational capabilities of a peculiar kind of state machine: min-heap automata. They were able to show Read More …
[Solved]: Why is the unary representation of a number exponentially larger than a base k representation of it?
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 …
[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 …
