Problem Detail: As seen in this recent XKCD strip and this recent blog post from Peter Norvig (and a Slashdot story featuring the latter), “regex golf” (which might better be called the regular expression separation problem) is the puzzle of defining Read More …
Author: ignougroup
[Solved]: Maximum degree of concurrency in task dependency graphs
Problem Detail: I’ve been researching ways of modeling and executing tasks which are dependent on each other (but in an acyclic way) and came up with task graphs. But the question that’s bugging me is how can I find out the Read More …
[Solved]: How to convert an NFA with overlapping cycles into a regular expression?
Problem Detail: If I understand correctly, NFA have the same expressive power as regular expressions. Often, reading off equivalent regular expressions from NFA is easy: you translate cycles to stars, junctions as alternatives and so on. But what to do in Read More …
[Solved]: Categorisation of type systems (strong/weak, dynamic/static)
Problem Detail: In short: how are type systems categorised in academic contexts; particularly, where can I find reputable sources that make the distinctions between different sorts of type system clear? In a sense the difficulty with this question is not that Read More …
[Solved]: How to go from a recurrence relation to a final complexity
Problem Detail: I have an algorithm, shown below, that I need to analyze. Because it’s recursive in nature I set up a recurrence relation. //Input: Adjacency matrix A[1..n, 1..n]) of an undirected graph G //Output: 1 (true) if G is complete Read More …
[Solved]: Time complexity based on two variables
Problem Detail: Suppose we have a function based on two inputs of length $m,n$. Therefore the time complexity of the function is calculated by $T(m,n)$. Suppose that we have: $T(m,c)in O(m^2)$ for any constant $c$. $T(c’,n)in O(n^2)$ for any constant $c’$. Read More …
[Solved]: Get the running time of forest disjoint sets
Problem Detail: If you have a forest implementation of disjoint sets, and have the union by weight/rank heuristic where you append the smaller one. Then why is the worst case running time Θ(m log n)? (m is the number of disjoint 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 …
[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]: 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 …
