Problem Detail: I am currently working through Tiernan’s paper, “An efficient search algorithm to find the elementary circuits of a graph” (published 1970), and I am stuck on point 3 of the following excerpt: The algorithm is named EC for “elementary Read More …
Category: Uncategorized
[Solved]: How to write this regular expression
Problem Detail: Consider the language over the alphabet $sum= {a}$ containing strings whose length is either a multiple of 2 or 3 (including the empty strings). Writing a regular expression for this language Asked By : Leroy Kayanda Answered By : Yuval Filmus Read More …
[Solved]: If a predicate is not computable, what can be said about its negation?
Problem Detail: Doing the following exercise: Let $overline{HALT(x,y)}$ be defined as $overline {HALT(x,y)} iff text{program number y never halts on input x}$ Show that it is not computable. Just want to make sure I have understood the concept correctly. We had Read More …
[Solved]: Push Down Automatons “guess” – what does that mean?
Problem Detail: I realize non-deterministic pushdown automata can be an improvement over deterministic ones as they can “choose” among several states and there are some context-free languages which cannot be accepted by a deterministic pushdown. Still, I do not understand how Read More …
[Solved]: Complexity of variation of partition problem
Problem Detail: I want to know whats the complexity of the following variant of the partition problem: Partition problem: http://en.wikipedia.org/wiki/Partition_problem Suppose we have one set formed by integers and we want to partition the set in two subsets of the same Read More …
[Solved]: Chernoff bounds and Monte Carlo algorithms
Problem Detail: One of Wikipedia examples of use of Chernoff bounds is the one where an algorithm $A$ computes the correct value of function $f$ with probability $p > 1/2$. Basically, Chernoff bounds are used to bound the error probability of Read More …
[Solved]: Creating arrays of object of abstract class in statically-typed object-oriented languages
Problem Detail: In statically-typed object-oriented languages (like Java, C++, C#, …), suppose I declare an abstract class: public abstract class myclass1 { …………….. } Most of these languages (like Java) wouldn’t allow us to create an Object of an Abstract class, Read More …
[Solved]: How do I continue learning programming, beyond the basics?
Problem Detail: DISCLAIMER: I understand that I might not be posting in the right part of StackExchange, or this question might have been asked before (I haven’t found it). If this offends anybody, I apologize. I’m 15 and a sophomore in Read More …
[Solved]: Showing that 3-colorable is NP-complete
Problem Detail: Just as a background, 3-colorable problem is as follows: Given a graph $G = (V, E)$, is it possible to color the vertices using just 3 colors such that no neighboring vertices have the same color? I’m aware we Read More …
[Solved]: FM-index – print all patterns
Problem Detail: How is it possible to print all patterns, of length k, contained in a string using FM-index and burrows-wheeler transform? PROBLEM DETAIL: I think it’s better to leave more details regarding my problem. The input i have are: the Read More …
