Problem Detail: Upon reading Do source code optimizers exist? I knew that such programs existed but the ones I have worked with use a set of rules to drive a transformation algorithm. Ira Baxter provided a link to the tools running Read More …
Blog
[Solved]: Give an example of a non-regular language $L$ such that $L^*$ is regular
Problem Detail: I can’t think of an example of a non-regular language $L$ such that $L^*$ is regular. . Any help ? Asked By : Altaïr Answered By : R B Define $L={a^nb^n|nin mathbb N}cup {a,b}$ It’s not hard to see that while Read More …
[Solved]: Why can’t hash tables provide O(n) sorting?
Problem Detail: Since a sufficiently large hash table takes constant time to both insert and retrieve data, should it not be possible to sort an array by simply inserting each element into the hash table, and then retrieving them in order? Read More …
[Solved]: Data structure to store sphere points (latitude,longitude) and retrieve all points within a distance
Problem Detail: I have a set of thousands~millions of points on a sphere’s surface, each with latitude, longitude. I want to quickly get all points within a distance d of a particular sphere point latC, lonC. The points are mostly concentrated Read More …
[Solved]: Hash-Table in Practice
Problem Detail: I have a set of $n$ values,$v_i$ and want to insert them into a hash-table, $HT$, in a way that each bucket (or hash-table cell) has at most $d$ values. I set $k=frac{n }{d}$, where $k$ is the number Read More …
[Solved]: Do you know of a brute-force algorithm for optimizing polynomial expressions?
Problem Detail: For instance, given the polynomial expression $xy + x + y + 1$ it will output $(x+1)(y+1)$. Thanks! Asked By : Fruitful Approach Answered By : user2566092 “Brute-force” in the context of factoring polynomials may involve factoring of integers, which is Read More …
[Solved]: Is a single symbol, not in a set, a language?
Problem Detail: I was reading about Turing machines and realized I’m not sure about the difference between the following scenario. Given the alphabet $Sigma = {a, b }$, we have the following assertions: $a in R $ ${a} in R$ I Read More …
[Solved]: What’s a fast algorithm to decide whether there is an $A_G$ corresponding to a given $chi_G(lambda)$?
Problem Detail: Given an adjacency matrix $A_G$ of an undirected graph $G$, it is easy and straightforward to compute the characteristic polynomial $chi_G(lambda)$. What about the other way around? The problem can be formulated as follows. Problem Given a polynomial $P$, Read More …
[Solved]: Partition problem with distinct integers
Problem Detail: Partition problem is a well known NP-complete problem. In the definitions I have seen, the input is assumed to be a multiset of integers and we want to decide the existance of a partition into two sets that have Read More …
[Solved]: What kind of reductions are usually used in order to prove PP-completeness?
Problem Detail: I’ve read that MAJSAT is PP-complete. Under what type of reduction is this true? What kind of reductions are usually used in order to prove PP-completeness? Asked By : Fayez Abdlrazaq Deab Answered By : D.W. Here “PP-complete” means “complete for Read More …
