# Questions tagged [algorithms]

A description of the specific steps needed to solve a particular problem in an unambiguous way, expressed in an abstract form.

459 questions
Filter by
Sorted by
Tagged with
2k views

### Volume of 3D convex hull of small point sets all on the hull

I have a question that is similar to this one asked before except in 3D, and I only need the volume, not the actual shape of the hull. More precisely, I'm given a small set of points (say, 10-15) in ...
8 views

### Dealing neighbor list in NVT Monte Carlo (MC) simulation

I'm making a NVT Monte Carlo (MC) simulation code with only short range interaction. I found many MC tutorial codes (usually Lennard-Jones system) in online. However, most of them are doing energy ...
105 views

### Efficient algorithm to decide if a graph is a cactus?

A cactus is a connected graph in which every edge belongs to at most one simple cycle. How should one modify the Depth First Search algorithm to obtain an efficient algorithm that determines if a ...
688 views

### Algorithm to compute the intersection of two lines given their cartesian equations

I'm looking for a way to compute the coordinates of the intersection of two lines. Each lines are defined with a point and a normal vector. We can assume than the normal vectors are not zero and ...
64 views

### Fast algorithm for computing cofactor matrix

I wonder if there is a fast algorithm, say ($\mathcal O(n^3)$) for computing the cofactor matrix (or conjugate matrix) of an $N\times N$ square matrix. And yes, one could first compute its determinant ...
28 views

### How is the D value being updated at simple RRT algorithm?

I am studying the following lecture (image) regarding 5 iterations of the simple RRT algorithm. I am trying to understand how each value is being updated regarding each iteration. I have figured out ...
71 views

### Chip testing problem

An engineer has n supposedly identical integrated-circuit chips that in principle are capable of testing each other. The engineer test jig accommodates two chips at a time. When the jig is loaded, ...
26 views

### A preconditioner for self-consistent iteration

I tried to derive a preconditioner for self-consistent iteration similar to section IX in arXiv:0804.2583. For simplicity, consider here only one orbital (one or two electrons) systems. Suppose that ...
8k views

### The easiest way to find intersection of two intervals

Right now I stuck with a problem. It seems to be really trivial one, but still it is hard for me to find an appropriate solution. The problem is: One has two intervals and are to find the intersection ...
369 views

### Fast algorithm for computing matrix square root using randomized linear algebra?

Is there a fast algorithm for computing the matrix square root of a real symmetric matrix using random matrices or randomized algorithms?
2k views

### Simulated Annealing proof of convergence

I implemented downhill simplex simulated annealing algorithm. Algorithm is very hard to tune, w.r.t. parameters including cooling schedule, starting temperature... My first question is about ...
129 views

### What is the name of the optimization algorithm that uses random sampling?

I am generating random weight as per e.g. below. The I generate a set of 3 values say 100, 250, 300 and I multiple them with the weights below Initial population. ...
389 views

### Drunken Man in Matlab

I wrote a script that plots the results of the "drunken lamppost" problem in MATLAB. Now I need to create a road-width from -3 to +3, length from 0 to infinity but the drunk can walk just ahead. It ...
4k views

### Is Fortuna or Mersenne Twister preferable as an algorithmic RNG?

A recent answer mentioned the use of Fortuna or Mersenne Twister Random Number Generators (RNGs) to seed a Monte Carlo simulation. I hadn't heard of Fortuna before so I looked it up - looks like it is ...
706 views

### Bin-packing: Maximise number of bins / “Fukubukuro” problem?

I recently encountered a problem that looks like a variation of bin packing or knapsack problem, but with the objective to maximise the number of bins/knapsacks: Consider there is a list of M items ...
247 views

### Testing for stability of a simulated dynamical system

Background and question I often work with simulations of dynamical systems and I usually track a single parameter $x$, such as the number of agents (for agents based models) or the error rate (for ...
238 views

### Traveling Salesman Problem

First off some context. The Traveling Salesman Problem(TSP) is to find the most efficient route passing through a series of points only once. However, there is no perfect function to solve for this in ...
54 views

### How to find a pair of divisors as close as possible to each other?

For a given integer $n\in\mathbb{N}^*$, I want to find a pair $(x,y)\in{\mathbb{N}^*}^2$ such that $x*y=n$ and $|y-x|$ is as small as possible. A naive algorithm I found is : ...
113 views

### Finding a shortest path in a graph

If each edge of a graph $G$ is unweighted or has equal weights, then the shortest path between two nodes in that graph is the path that contains the fewest number of edges. Such a path can be obtained ...
74 views

### Find a vector B that minimizes |W-A*B|

I want to find a candidate vector $B$ that $$\min|(W - A_i * B_i)|$$ $$a_i > 0,\ A_i=\{a_0,...,a_i\},\ B_i=\{-1,0,1\}^i$$ For example, given $$W = 0.6,\quad A_4 = [0.1, 0.2, 0.4, 0.7]$$ one ...
36 views

### Single-variable multimodal derivative-free optimization (for a well-behaved function)

Are there well-established approaches to single-variable multimodal optimization? Given $f:\mathbb{R}\rightarrow\mathbb{R}$ that: has several local minima within a given range of interest $[a,b]$ is ...
70 views

### How to justify using available code (in different language) for comparing algorithms

I have proposed an algorithm for a scheduling problem in a submitting paper. In the revision, the reviewer asked us to compare with another algorithm from the literature. Our algorithm is in MATLAB, ...
106 views

### Clustering with points lying along different 3D planes

I have a bunch of data points in 3D that lie along a few planes. What would be the best approaches to estimate the normals of these planes? Edit: There are roughly equal number of points lying along ...
139 views

6k views

### Python implementations of Gillespie's direct method

I'm looking for a decent implementation of Gillespie's Direct Method in Python, as if I code the algorithm myself I'm nigh positive I'll do it inefficiently. Anyone have a favorite?
19 views

### Binary tree for 2 elements [closed]

I want to understand Binary Search for 2 element list made of 1,2. I draw a tree as below. Is it correct? If I want to search for an element 2, it will make 2 comparisons. If I want to search for ...
294 views

### Discrete-time Algebraic Riccati Equation (DARE) solver in C++

I need to use a Discrete-time Algebraic Riccati Equation (DARE) solver for an embedded controller (with limited processing power) in a research project and sadly, I can't find any implementation of it ...
2k views

### Markov (Chain) image generators?

Markov Chains can be used to generate, or auto-complete, text. https://en.wikipedia.org/wiki/Markov_chain#Markov_text_generators Training text is read, and some information about the text is ...
57 views

### Where does the seemingly official number of certain algorithms come from?

There are a lot of algorithms which seem to have been supplied an official number, such as Algorithm 76, Hierarchical clustering using the minimum spanning tree. Another example is Algorithm 123, ...
60 views

### tea bag flavors mixing algorithm [closed]

I bought three boxes of tea bags with different flavors (A, B, C). I wish to mix them in such a way that - there is never two consecutive bags of the same flavor (ABCCAB is avoided) ; - the mixing ...
94 views

### FFT-based Image Rotation Algorithms More Accurate Than Chirp-Z?

We're currently using a Chirp-Z based implementation: R. W. Cox and R. Tong, "Two- and three-dimensional image rotation using the FFT," IEEE Trans. Image Processing, vol. 8, no. 9, pp. 1297–1299, Sep....
361 views

### Matching/Assignment Problem

I'm not sure how I can represent and solve the following problem. I have a list of sales (timestamp and quantity) and a list of corresponding inventory draws (timestamp and quantity). What I ...
9k views

### How to solve block tridiagonal matrix using Thomas algorithm

Thomas algorithm can be used to solve a tridiagonal matrix:  \begin{bmatrix} {b_ 1} & {c_ 1} & { } & { } & { 0 } \\ {a_ 2} & {b_ 2} & {c_ 2} & { } & { }...
95 views

### Accurate and efficient computation of the inverse Langevin function

The Langevin function $\mathcal{L}(x) = \mathrm{coth}(x) - \frac{1}{x}$ occurs in computations related to elastomers and paramagnetic materials. It is easily computed accurately and with high ...
72 views

### Pivoting in Block LU

What are common methods to choose pivot blocks in Block LU (for non-SPD/non-Diagonally Dominant Matrices)?
72 views

### Kernel independent fast multipole method for Yukawa potential [closed]

Has anybody used the KIFMM (https://web.stanford.edu/~lexing/fmm.pdf) for the Yukawa potential?
75 views

### Ranking Sewer Lines worst to best condition using Genetic Algorithm?

Problem I work for a municipality and we are trying to figure out which sections of sewer lines to replace first or at least identify areas that should be looked at. It was suggested I use a Fast ...
175 views

### Use of Morton Key to reduce number of grid points

I asked a question on Stack Overflow Performance Issue with VP Trees and Nearest Neighborsand I was not satisfied with the answer and so I thought I would reword my question for this site and post ...