Problem Detail: I have started reading on algorithmic complexity for my thesis work. Already have studied on Polynomial time reducibility, NP-Complete, NP-Hard. Now trying to prove NP completeness of some of the classical problems. I have started with 3-SAT problem. 3-SAT Read More …
Author: ignougroup
[Solved]: Equivalence of two context free grammars [for the given example]
Problem Detail: I know that in general it is undecidable whether two context free grammars generate the same language, but I have to do this exercise and I am finding myself somewhat stuck: G1: S->e|aB|bA B->bS|aBB A->aS|bAA G2: S->e|aSb|bSa|SS I tried Read More …
[Solved]: Is it possible to always construct a hamiltonian path on a tournament graph by sorting?
Problem Detail: Is it possible to always construct a hamiltonian path on a tournament graph $G=(V,E)$ by sorting (using any sorting algorithm) with the following total order: $qquad displaystyle a leq b iff (a,b) in E lor left(exists, c in V. Read More …
[Solved]: Binomial coefficient to approach multi-way choices DP problem?
Problem Detail: I’m trying to understand this dynamic programming related problem, adapted from Kleinberg’s Algorithm Design book. Not homework: i’ve already a solution, just considering if i’m ok with the theory. Suppose we want to replicate a file over a collection Read More …
[Solved]: What does up arrow ($uparrow$) mean in pseudocode?
Problem Detail: I’m learning vantage point trees, and I met this while reading the paper Data Structures and Algorithms for Nearest Neighbor Search in General Metric Spaces by Peter Yianilos (Proceedings of SODA 1993, SIAM, pages 311–321; PDF). The following pseudocode Read More …
[Solved]: kd-tree stores points in inner nodes? If yes, how to search for NN?
Problem Detail: The link in wikipedia about kd-trees store points in the inner nodes. I have to perform NN queries and I think (newbie here), I am understanding the concept. However, I was said to study Kd-trees from Computational Geometry Algorithms Read More …
[Solved]: Algorithm for sorting with constraints
Problem Detail: I’ve got 30 elements which has to be grouped/sorted into 10 ordered 3-tuple. There are several rules and constraints about grouping/sorting. For example: Element $A$ must not be in the same tuple same unit $B$. Element $C$ must not Read More …
[Solved]: Reference request: optimizing procedures on lists in dynamic languages by performing safety checks in advance
Problem Detail: For my science fair project, I implemented an optimization to Python’s sort routine. The idea is to move the safety checks that have to be carried out during each comparison, e.g. type checks and character-width checks, outside of the Read More …
[Solved]: Suboptimal Solution for a combinatorial problem
Problem Detail: I have a cost function $f(X)=|hat{X}-X|_2$ to minimize which depends on a $stimes s$ matrix $X$ where $hat{X}$ is given and $|X|_2=big(sum_{i,j}x_{ij}^2big)^{1/2} $. This matrix $X$ is generated by selecting only $s$ different rows from a matrix $B$ of Read More …
[Solved]: I want to pursue a career in computer programming. Where do I start?
Problem Detail: I am currently finishing up my junior year as a Biochemistry major at a 4-year university. In a year, I will graduate with a B.S. in Biochemistry and way more credit hours than anyone should ever have due to Read More …
