The 2024 Developer Survey results are live! See the results

# Questions tagged [implementation]

Questions relating to implementations of algorithms

31 questions
Filter by
Sorted by
Tagged with
1 vote
89 views

### Is it possible to define beta reduction for PHOAS?

I'm using Parametric Higher-Order Abstract Syntax (PHOAS) as a representation for untyped lambda calculus in OCaml: ...
• 105
1 vote
147 views

### Looking for an implementation of any PCP-verifier for any NP problem

Is there any implementation of any PCP-verifier (for any NP problem) researchers can download and test? No matter if it is a github entry with actual downloadable code or just a (reasonably detailed) ...
1 vote
69 views

### Operations on Sentential Decision Diagrams

I've been recently reading about decision diagrams and their variants and came across sentential decision diagrams (paper here http://reasoning.cs.ucla.edu/fetch.php?id=121&type=pdf). The paper ...
• 113
1k views

### Algorithm for finding a 3-cycle cover

Given: An undirected, unweighted graph Looking for: A disjoint vertex cycle cover where every cycle has at least 3 edges Is there any algorithm that solves this problem, possibly with some ...
72 views

### Has Khachiyan/Porkolob's convex integer optimization been implemented?

Khachiyan and Porkolab in 'Integer optimization on convex semialgebraic sets' gave an $O(ld^{ O(k^4)})$ algorithm to minimize a degree $d$ form with integer coefficients of binary length at most $l$ ...
• 13.1k
179 views

### Practical polynomial-time implementation of bounded degree graph isomorphishm

There's a well-known article for solving graph isomorphism problem in polynomial time. Many other articles on the subject of isomorphism mention it as a possible "alternative", but note that is not ...
• 137
196 views

### Use of physical environment to obtain useful results

I dare to ask a broad layman question expecting a layman simple answer. I'm no scientist in any field. Question: Does the following concept make sense or does it exist and actually being used? > ...
• 201
493 views

### Word length using entropy : Maximum entropy criteria

The question is based on research paper titled, Markovian language model of the DNA and its information content In the supplementary document, the Authors show how they determine the word length of ...
• 141
552 views

### Most efficient inplace merge algorithms (stable and unstable)

I am currently researching the best algorithms available to achieve an inplace merge operation: consider two consecutive sorted arrays of size n and ...
• 307
316 views

### Implementation of partition trees?

Have partition trees ever been implemented? Here, I'm talking about the partition trees from computational geometry. The earliest (near-)optimal versions of which were due to Matousek and others, ...
• 571
933 views

### Implementation of surreal numbers for games

There is a very nice construction by Conway of surreal numbers. They are "numbers" that contain both real numbers and ordinals, are totally ordered, and have all the properties of a field (except they ...
• 8,883
197 views

### Are there any implementations of a graph crossing algorithm?

This is much more focused version of this question: Are there good implementations for easy subclasses of NP-hard graph problems Computing the graph-crossing number $cr(G)$ for a simple graph is ...
• 365
283 views

### A good Library for testing whether a minors exists in a graph?

I would like to know if there are any free graph libraries for testing whether a specific set of minors exists in a given graph?
• 289
499 views

### Implementation of Kallmann's Dynamic Constrained Delaunay Triangulation algorithm

Does anyone know of any open source implementation (preferably in java) of Kallmann's DCDT algorithm? If there's another DCDT algorithm that has been implemented, that may work as well. I wasn't sure ...
• 393
292 views

### Implementations of Undirected Disjoint Paths

I'm looking into the Undirected Vertex Disjoint Paths problem: Given a list of tuples of vertices (s_i, t_i) Find simple, pairwise disjoint paths P_{s_0,t_0}, P_{s_1,t_1}, ... that connects ...
• 958
136 views

### How would you define a set of 'fundamental operations' over an object? [closed]

I'm writing an implementation for a common array structure. As you would find already familiar, an array is an ordered data structure that you can transform with different (hopefully self-explained) ...
• 125
337 views

### Are there any implementations for zero-knowledge proofs of NP-complete problems?

It's been known for a long time that any claim in NP has a zero-knowledge proof for it. Has anybody actually implemented a zero-knowledge proof system for a NP-complete language? Using a search engine,...
2k views

### Implementation that solves minimum set cover

Does anyone know of any tools that solve the approximate minimum set cover problem? I know of the greedy algorithm (which is straightforward to implement myself), but I've also been reading about ...
• 12.3k
839 views

### Implementation of Wilf-Zeilberger and related methods

The book A=B by Petkovsek, Wilf and Zeilberger describes algorithms to compute different sums of binomials. AFAIK, these algorithms are still being improved by different authors. Do you know where ...
• 4,513
2k views

### Any existing Reeds-Shepp implementations?

Does anyone know of any open source implementations for finding the optimal path of a Reeds-Shepp car? I'm trying to implement the formulas myself, but I'm having trouble with one of them. I think it'...
• 131
1 vote
383 views

### Implementation of a Logical Hierarchical Hidden Markov Model

Is anyone aware of any implementations of algorithms for learning and/or processing a Logical Hierarchical Hidden Markov Model, as described in this paper? I've found dozens of papers about Logical ...
• 127
179 views

### Implementable algorithm for Voronoi regions with obstacles

I'm looking for an algorithm that computes the Voronoi regions of a set of points contained in a polygonal region with obstacles. What would be the most simple, straightforward way to implement this? ...
• 161
693 views

### Implemented code to compute pathwidth (= Node search number, vertex separation number, interval thickness)

I am looking for an implementation of an algorithm to compute the pathwidth of a graph. It is well known that computing the pathwidth is equivalent to computing the node searching number, vertex ...
• 5,275
1 vote
213 views

### Computational Library to compute Quantum Cluster States

I want to write a simulator for a quantum computing model that I am working on and I was wondering what would be the correct library / implementation strategy to implement quantum cluster states? ...
• 1,661
356 views

### Are there good implementations for easy subclasses of NP-hard graph problems

Given graph G = (V,E) I need to solve some problems that are NP-Complete on G. However it could be that G belongs to some class where these problems has polynomial solutions (here is a great resource ...
• 531
302 views

### Explain 0-extension algorithm

I'm trying to implement an approximation algorithm for the 0-extension problem I found the following paper: Approximation Algorithms for the 0-extension problem by Gruia Calinescu, Howard ...
• 169
2k views

### Best book on Simplex Method implementation?

I'm interested in implementing SM for LP task, however I've heard about possible pitfalls: Cormen's book says that it is possible to have input data which will make naive implementation to behave in ...
• 551
1k views

### Powerful algorithms that are just too hard to implement-- how to be sure they are right?

I am referring to the question here: powerful algorithms too complex to implement. If an algorithm is powerful, but too complex to implement, how can you be sure that the algorithm is correct? ...
• 409
17k views

### Powerful Algorithms too complex to implement

What are some algorithms of legitimate utility that are simply too complex to implement? Let me be clear: I'm not looking for algorithms like the current asymptotic optimal matrix multiplication ...