# Raphael

Kaiserslautern, Germany

lmazy.verrech.net

Age: 26

I am a PhD student at the Algorithms & Complexity group at University of Kaiserslautern, Germany. I research design and analysis of parallel algorithms and data structures.

In my free time I read books, enjoy (and sometimes make) music, code, work out and roam the webs.

You can find sources for all self-created images I post on Stack Exchange here.

 3m comment Is $O(N+M)$ exponential or polynomial?See also here. 5m comment disproving big omega problemWithout any attempt on your part it is impossible to tell what your problem is. Please visit our reference question which should contain all you need to know. (By the way, you don't have to show that $g(n) < cf(n)$; it's not a necessary criterion for $g \not\in \Omega(f)$. It's certainly sufficient, though, but do you know why?) 2h comment How do I show T(n) = 2T(n-1) + k is O(2^n)?I don't think the practices in TCS research papers should inform the level of detail in teaching. The face that experts communicate like this does not mean that it's a formal proof, and it does also not mean that beginners will understand and learn from it. (Also, there are many, many stories of similar sentences being blatantly wrong because some people don't seem to bother to check their statements rigorously before putting shortened versions in space-restricted papers. But that's a discussion for [academia.SE].) 2h revised How to approach NFA design questions intuitively?tightened question a bit 2h answered How to approach NFA design questions intuitively? 3h comment How do I show T(n) = 2T(n-1) + k is O(2^n)?Nitpicking: $\dots$ is not a formal proof, an induction is still necessary. It's a good way to generate guesses, though. 3h comment How do I show T(n) = 2T(n-1) + k is O(2^n)?It's also in $O(n!)$. What's special about $2^n$? Do you want $\Theta$? Have you checked out our reference question on solving recurrences? 20h revised Is Co-NP closed under taking subset?edited tags 1d comment Why does a regular expression only accept all my required strings when the concatenation is the first of the OR operations?You can force most real-world regexp matchers to match an expression R against the whole input (line) by modifying it to ^(R)$ (creating a new capture group). 1d comment How to convert a DFA to a Turing machine?@zinking Not true. Only Turing machines are Turing machines. 1d comment Relative complement of a Non CFL to CFLDoes this answer your question? Shall we close it or should @HendrikJan post an answer? 1d revised Redundant States During Removal of Null-Moves (Regular Expression to DFA)LaTeXified image maths 1d comment If I ask a question asking for test cases would that get closed?@GuyCoder Deciding which question is useful to (many) others is not always easy. Test cases for a homebrew implementation of a niche/homebrew algorithm: definitely too localized. How to test a given well-known (abstract) algorithm that is widely used: probably fine, if there are specific problems. If you just you want a list "important algorithm -> test bank", that's not good for SE but for a Wiki or a Github repository for machine readable files (or even a decicated site). (Btw, if you want to ensure correcteness, no amount of testing will help. Prove it, e.g. with Coq or Isabelle/HOL.) 1d answered If I ask a question asking for test cases would that get closed? 1d comment Redundant States During Removal of Null-Moves (Regular Expression to DFA)Please don't just put images of text here, and without attribution at that! a) give a proper reference to the book you are using. b) type all text/maths again (you can use LaTeX) c) cut the images you drew yourself in parts and integrate them into the structure. d) Finally, check the algorithm the book uses. I'm sure there is one. 2d comment If I ask a question asking for test cases would that get closed?Is getting/generating test cases a(n interesting) computer science problem or are you "only lazy" (no offense intended, being lazy is a legitimate strategy)? 2d revised Are there problems with complexity between$O(n^c/\log^b n)$and$O(n^{c - \varepsilon})\$?edited tags; edited title 2d comment Getting Forwarding Table for Bridges connecting a number of LANsAlso, please don't use images without attribution. First, the quality is bad; second, they can not be found by search; third, you should always give credit to your sources. 2d comment Getting Forwarding Table for Bridges connecting a number of LANsThis is a dump of a homework/exercise problem, not a question. If you have a specific question regarding the wording of the problem or about concrete steps in your own attempts at solving the problem, feel free to edit accordingly and we can reopen the question. See also here for our homework policy, and here for a relevant discussion. 2d awarded Nice Question