IgnouGroup Social Campus
Problem Detail: Has anyone studied the problem of converting a generic flowchart to a semantically equivalent “structured flowchart” (i.e. one that only uses the ‘if’ and ‘while’ block structure)? I can see this may be relevant to code generation and optimization Read More …
Problem Detail: From an initial set $S$ of 2D points, how to efficiently compute a minimum(-size) dominating subset $M$ ? $M$ is a dominating subset of $S$ if for any $(x,y)$ in $S$ there is at least one point (a,b) in Read More …
Problem Detail: I know that if one-way functions exist then there are certain universal one-way functions that exist, but to my knowledge they are too impractical to implement (which is the main reason why they are not being used in modern Read More …
Problem Detail: I am studying the proof of the following theorem: Given the language $mathit{REGULAR}_mathit{TM} = {langle M rangle | M $ is a turing machine and $mathit{Accept}(M)$ is regular$}$ $mathit{REGULAR}_mathit{TM}$ is undecidable. The proof given in Sipser shows that if Read More …
Problem Detail: A recent puzzle blog post about finding three evenly spaced ones lead me to a stackoverflow question with a top answer that claims to do it in O(n lg n) time. The interesting part is that the solution involves Read More …
Problem Detail: I’d really like your help with proving the following. If $mathrm{NTime}(n^{100}) subseteq mathrm{DTime}(n^{1000})$ then $mathrm{P}=mathrm{NP}$. Here, $mathrm{NTime}(n^{100})$ is the class of all languages which can be decided by nondeterministic Turing machine in polynomial time of $O(n^{100})$ and $mathrm{DTime}(n^{1000})$ is Read More …
Problem Detail: $A=${$ ⟨M⟩$:$M$ $is$ $a$ $Turing$ $Machine$ } What can be said about $A$ ? Specifically, is $A$ decidable,regular,CFL,CSL? I would say $A$ is decidable since we can write an algorithm to check whether a string is a valid encoding Read More …
Problem Detail: Reading about superdense coding I came upon a calculation I can not understand. We have an EPR entangled pair of qubits $frac{1}{sqrt2}(|00rangle + |11rangle)$ and we want to apply a Pauli X gate to the first of the entangled Read More …
Problem Detail: Suppose there is a CFG with the rules S–> Aa A–> Bb B–> A B–> Epsilon To my best understanding the left most derivation would go like this.. S==> Aa ==> Bba ==> Aba ==> Bbba ==> bba or Read More …
Problem Detail: You are given a bunch of nodes evenly spaced in a rectangular grid. The rectangle is M nodes long and N nodes wide. Node A is in the upper left hand (northwest) corner and node B is at the Read More …
