Computer Science Weekly Newsletter
Computer Science Weekly Newsletter

Top new questions this week:

Finding examples of languages that are "anti-palindromic"

Let $\Sigma = \{ 0, 1 \}$. A language $L \subseteq \Sigma^* $ is said to have the "anti-palindrome" property if for every string $w$ that is a palindrome, $w\notin L$. In addition, for every string ...

asked by Marik S. 7 votes
answered by Shreesh 7 votes

Why is FACTOR in Co-NP?

I'm having trouble wrapping my head around the problems PRIME, COMPOSITE, FACTOR and how they're related in terms of complexity. I understand that PRIME has been shown to be in $P$ by the AKS ...

complexity-theory factoring  
asked by Fequish 6 votes
answered by Yuval Filmus 6 votes

Relationship of algorithm complexity and automata class

I have been unable to find a graph depicting or text answering the following question: Is there a direct relationship between the complexity of an algorithm (such as best / worst case of quick sort), ...

complexity-theory automata reference-request complexity-classes  
asked by Harpo Roeder 5 votes
answered by jmite 5 votes

String searching, where we allow characters to almost-match

Let $\Sigma= \{1,...,n\}$. Let $T$ and $Q$ be two strings with characters from the alphabet $\Sigma$ of lengths $n,k$, respectively. I am looking for an algorithm to test whether $Q$ appears as a ...

algorithms strings string-metrics substrings  
asked by Eric_ 5 votes
answered by D.W. 2 votes

Voronoi cells for rectangles

I am looking for a reference on the following variant of a Voronoi diagram: Instead of seed points, there are seed rectangles which are axis-parallel and pairwise-disjoint. Instead of Euclidean ...

reference-request computational-geometry  
asked by Erel Segal-Halevi 4 votes
answered by Shreesh 1 vote

Finding a way out of a polygon

There is a simply-connected polygon $C$. It contains $n$ pairwise-interior-disjoint simply-connected polygons, $D_1,\dots,D_n$: The goal is to select one of the polygons, say $D_i$, and attach to ...

reference-request computational-geometry  
asked by Erel Segal-Halevi 4 votes
answered by Shreesh 5 votes

Why does garbage collection extend only to memory and not other resource types?

It seems like people got tired of manual memory management, so they invented garbage collection, and life was reasonably good. But what about every other resource types? File descriptors, sockets, ...

garbage-collection resource-allocation  
asked by mindreader 4 votes
answered by Brian Hibbert 2 votes

Greatest hits from previous weeks:

Proof that dead code cannot be detected by compilers

I'm planning to teach a winter course on a varying number of topics, one of which is going to be compilers. Now, I came across this problem while thinking of assignments to give throughout the ...

computability proof-techniques compilers  
asked by thomas 24 votes
answered by jmite 50 votes

Regular Expression for even-odd language of string

I am new to Automata theory and would to make a regular expression for "even-odd" strings, defined over $\Sigma = \{a,b\}$, which is the set of strings with even numbers of $b$'s and odd number of ...

automata regular-expressions  
asked by Khurram Ali 1 vote
answered by Ran G. 5 votes

Can you answer these?

Finding if a feasible flow exists in a minimum cost flow problem

I've been trying to understand the generic methodology for finding a flow with a certain value (satisfying all demand criteria) with a minimum corresponding cost. I know that this might sound somewhat ...

algorithms graph-theory network-flow  
asked by Zsolt 1 vote

local addresses in segmentation

I'm reading "Understanding Linux Kernel 3rd edition" and it starts talking about memory segments. It says that a logical address is: Included in the machine language instructions to specify the ...

asked by Gatonito 1 vote

Program interpretation for static analysis

Are there any implementations, or even academic work, regarding an application capable of looking at code and inferring what the code actually intends to do? For example, we give it a program that ...

artificial-intelligence compilers type-theory type-inference  
asked by wizzardOfOz 1 vote
Subscribe to more Stack Exchange newsletters

Unsubscribe from this newsletter or change your email preferences by visiting your subscriptions page on

Questions? Comments? Let us know on our feedback site. If you no longer want to receive mail from Stack Exchange, unsubscribe from all emails.

Stack Exchange, Inc. 110 William St, 28th Floor, NY NY 10038 <3