Problem Detail: Aren’t there $n^2$ unique substrings of a string (irrespective of the alphabet size)? Perhaps the number of unique suffix substrings is less than the number of unique substrings of a string. Asked By : Wuschelbeutel Kartoffelhuhn Answered By : A.Schulz For Read More …
Blog
[Solved]: Understanding the definition of reduction
Problem Detail: From Wikipedia: Given two subsets A and B of N and a set of functions F from N to N which is closed under composition, A is called reducible to B under F if $$ exists f in F Read More …
[Solved]: How To Best Learn About Algorithms In Depth
Problem Detail: I have been reading this site with a great deal of interest, but I find a lot of it goes over my head. This has made me wish to learn a lot more about algorithms and CS in general. Read More …
[Solved]: Efficient algorithm to compute the $n$th Fibonacci number
Problem Detail: The $n$th Fibonacci number can be computed in linear time using the following recurrence: def fib(n): i, j = 1, 1 for k in {1…n-1}: i, j = j, i+j return i The $n$th Fibonacci number can also be Read More …
[Solved]: Proving that $A vee (neg A wedge B) equiv A vee B$
Problem Detail: I’m reading a book at the moment about logic gates and Boolean simplification. There is a part which I can’t seem to follow. I can easily work out that $A vee (neg A wedge B) equiv A vee B$ Read More …
[Solved]: Build a regular grammar for a regular language
Problem Detail: The language considered is the infinite set of all chains that meet the following conditions. Conditions: 1) They consist of symbols from the set {1,a,b}. 2) They always start with the subchain ‘1a’. 3) They always include at least Read More …
[Solved]: Prove that the language of unary not-prime numbers satisfies the Pumping Lemma
Problem Detail: Here is a question from Daniel I. A. Cohen’s book Introduction to Computer Theory: Consider the language: $quad mathrm{PRIME}’ = { a^n mid n text{ is not a prime} } = { varepsilon, a, aaaa, aaaaaa, aaaaaaaa, ldots }$ Read More …
[Solved]: Is Logical Min-Cut NP-Complete?
Problem Detail: Logical Min Cut (LMC) problem definition Suppose that $G = (V, E)$ is an unweighted digraph, $s$ and $t$ are two vertices of $V$, and $t$ is reachable from $s$. The LMC Problem studies how we can make Read More …
[Solved]: Non-deterministic Turing machine and palindromes
Problem Detail: I have to design a Non-deterministic Turing machine that accepts only non-palindromes in $NTime(nlog n)$. I think this would be easy on a 2-tape DTM. Simply copy the string onto the second tape – $O(n)$ time – and then Read More …
[Solved]: What does this definition of a Primary key mean?
Problem Detail: My text book gives the following definition of a primary key in a relational database, which I don’t entirely understand. Help would be greatly appreciated. Let $R$ be a relation. Then the primary key for $R$ is a subset Read More …
