Questions tagged [algorithm]
An algorithm is a sequence of well-defined steps that define an abstract solution to a problem. Use this tag when your issue is related to algorithm design.
388
questions with no upvoted or accepted answers
19
votes
0answers
305 views
Multiplying big numbers using Karatsuba's method
The Karatsuba algorithm, first published in 1962, aims to speed up the multiplication of big numbers by reducing the number of 'single-digit-multiplications' involved.
Because of its complexity (...
8
votes
0answers
155 views
Implementing Simple Diff in Rebol
I've taken a crack at implementing Simple Diff in Rebol (versions 2 and 3). Simple Diff works by finding the longest common sequence in two series, then recursively applies itself either side of this ...
7
votes
0answers
149 views
Metropolis Monte Carlo Sampler in Rust
the following is an implementation of the standard Metropolis Hastings Monte Carlo sampler. You can read more about it here.
At the end I am going to give you a link to the Rust playground, so you ...
7
votes
0answers
387 views
A* Algorithm in F#
Inspired by this post I looked up A* on wikipedia and went on with my own implementation as seen below where I try to mimic the pseudocode on Wikipedia but in a recursive manner.
I would like any ...
6
votes
0answers
349 views
Recursive and iterative implementation on Kosaraju algorithm
Kosaraju algorithm is mainly phrased as two recursive subroutines running postorder DFS twice to mark SCCs with linear time complexity O(V+E) below,
For each vertex u of the graph, mark u as ...
6
votes
0answers
136 views
General algorithm to calculate sums of all subsets of a given sequence of numbers
Background
A recent question Print sums of all subsets made its way to the Hot Network Questions list. The problem is simple:
Print sums of all subsets of a given set
Given an array of ...
6
votes
0answers
189 views
Selection sort with reduced comparison count: Python iteration 2
Follow up to Selection sort with reduced comparison count - semi-final Iteration?
My goal (and excuse not to tag reinventing…) is to have presentable code to argue the viability of reducing the number ...
6
votes
0answers
7k views
Implementation of Single Layer Perceptron Learning Algorithm in C
I have implemented a working version of perceptron learning algorithm in C. Right now, it only works on single layer perceptrons and only takes two inputs.
I plan on making it work with more than two ...
6
votes
0answers
142 views
Unstructured quantum search algorithm for unknown solutions
This code was tested on IBM's 5-Qubit processor as an implementation of Grover's search algorithm, but for an unknown number of solutions. This code is based on Arthur Pittenger's book, "An ...
6
votes
0answers
414 views
Fowler–Noll–Vo hash function in Lua
I recently coded this FNV-1a hash function in Lua. Are there any apparent performance improvements that could be implemented?
...
6
votes
0answers
402 views
Translating CFRM algorithm from Java to Clojure and improving performance
Counterfactual Regret Minimization is an algorithm that can be used to find the Nash Equilibrium for games of incomplete information. I have tried to adapt the exercise from here to Clojure. You can ...
5
votes
0answers
42 views
calculating upper bound on normalized weighted levenshtein distance
Current implementation
I am using a normalized weighted Levenshtein distance for two utf32 strings with the following costs (insertion: 1, deletion: 1, replacement: 2). The normalization is performed ...
5
votes
1answer
121 views
Converting a float to a fraction as a string
I was inspired by this video by Matt Parker to use the Farey Sequence to convert a float into a string representation of a fraction, how did I do? How well did I follow F# workflow and patterns (I'm ...
5
votes
0answers
66 views
K nearest neighbours algorithm
Here is a project that I worked on for a few days in June 2020. Since the algorithm is extremely slow, I looked into methods in order to parallelize operations but did not obtain any satisfactory ...
5
votes
0answers
106 views
Selecting child contours in OpenCV
I'm really new to OpenCV. :) I have been working on this for almost an entire day. After hours of sleepless work I would like to know if I can further improve my code.
I have written some code to ...
5
votes
0answers
294 views
Mahjong hand completeness checking algorithm
As a summer project, I have been working on a small-scale, console-based version of Mahjong (the Rummy-like hand completion game, and not the solitaire version). While having prior knowledge of the ...
5
votes
0answers
214 views
Rabin-Karp algorithm implementation
This code uses the Rabin-Karp algorithm to compare two text files. It takes a few minutes when both files contain around 1000 words. How can it be improved?
...
5
votes
0answers
57 views
Iterate over the solutions for minimum cost matching
I implemented this paper, more specifically the bipartite graph case in numpy.
The whole code is available on github.
The file munkres.py comes from scipy.
Some ...
5
votes
0answers
429 views
Backtracking solver for n queens problem and knight's tour
Playing with https://ocaml.org/learn/tutorials/99problems.html#Miscellaneous-Problems I wrote a backtracking solver for the n queens problem, then the knight's tour, and realised I could generalise ...
5
votes
0answers
44 views
Macao, a General Game Playing AI library - Game state goes in, best move comes out
I'm working on a simple General Game Playing AI library. The idea is that it should work with almost any kind of game, with a minimum of configuration. At the moment, I have it working on 2 player ...
5
votes
0answers
212 views
5
votes
0answers
78 views
Optimally splitting a text into strings from a set
I am trying to write an algorithm that starts with a corpus of texts (e.g., a Wikipedia dump). It first builds an array of individual characters (e.g., "a", ...
5
votes
0answers
765 views
Implementation of DBSCAN in C++
I've recently just finished my implementation of a DBSCAN in C++ for a machine learning framework. I've tried to follow the pseudocode implementation on Wikipedia as best I could. I also found some ...
5
votes
0answers
159 views
Assembling and traversing a graph, given a list of items and parent pointers
I've written a function which takes input such as this:
...
5
votes
0answers
241 views
Equivalent binary trees (structure & values)
I am following the Golang tour and I have been asked to build a couple of functions to manipulate binary trees.
My code runs as expected, but I would like to know if I could further improve my code. ...
4
votes
0answers
205 views
Optimizing recursive backtrack search algorithm in Skyscraper puzzle
I'm trying to solve a skyscraper puzzle for 6x6 boards using constraint programming and then backtracking. My solution works but is too slow, for certain cases, it takes up to 2 seconds and I was ...
4
votes
0answers
66 views
Naive Solver of Matrix with Periodic Boundary Conditions Feedback
I am creating an \$O(n)\$ solver for an \$Ax = b\$ system where \$A\$ has the form
\$
A = \begin{pmatrix}
a_1 & b_1 &&&d_{u}\\ c_1 & a_2 & b_2\\& \ddots & \ddots &...
4
votes
0answers
69 views
Integrator 2.0: A Simple Integrator in C++17
This is a follow up of A simple definite integrator class of a single variable in C++
I took most of the advice from the user: emma-x and some from user: sudo-rm-rf-slash
Here is my fully revised ...
4
votes
0answers
189 views
JavaScript AVL Tree
I have been working through Introduction to Algorithms 3rd Edition, and have implemented an AVL tree through prototypal inheritance. The code presented here does work as expected based on the tests ...
4
votes
0answers
114 views
Rust Iterative and Recursive Merge Sort Implementation
I'm in the process of learning both Rust and algorithms after primarily focusing on web development. As such I've had a go at implementing merge sort both iteratively and recursively.
I've looked for ...
4
votes
0answers
70 views
Identifying the missing number in an array
This is from LeetCode:
Missing Number
Given an array containing n distinct numbers taken from 0, 1, 2, ...,
n, find the one that is missing from the array.
Example 1:
Input: [3,0,1]...
4
votes
0answers
171 views
Strongly Connected component algorithm implementation(Python)
My goal is to implement Strongly Connected Components algorithm using python.
I have splitted up my code on 3 parts:
Data Load:
...
4
votes
0answers
201 views
Chess AI Using Minimax and Alpha-Beta Pruning
I am working on a Chess AI using chess.js, and currently, it can run 3 layers in under 10 seconds, but 4 or more takes minutes. How can I optimize my current code to be able to run 4 or 5 layers, or ...
4
votes
0answers
470 views
RGB to YCbCr conversion in Java
I found a Go language code to do RGB to YCbCr conversion from here! I ported it to Java:
...
4
votes
0answers
60 views
Array Search Algorithm
Recently, I've been experimenting with an array searching algorithm that I'm not sure I've seen anywhere (minor references here).
I'm still not fully-learned on how to state the efficiency of what I'...
4
votes
1answer
90 views
Modelling Immerman–Szelepcsényi in Haskell
I am trying to model the proof of Immerman–Szelepcsényi Theorem with Haskell since it heavily uses non-determinism. An explanation of what the point of this is can be found here.
...
4
votes
0answers
91 views
Improved Knuth-Morris-Pratt over a source of indeterminate length
Following the successful review of my previous implementation.
Please review my new, generic implementation of the Knuth-Morris-Pratt algorithm. Its modified to search a source of indeterminate ...
4
votes
0answers
2k views
Design an object oriented parking lot
I solved this system design interview question.
The problem description
Design a parking lot
Constraints and assumptions
What types of vehicles should we support?
Motorcycle, ...
4
votes
0answers
46 views
Functional blob counting
I have image files consisting of black and white pixels encoded as RGB8. I want to count the number of blobs i.e. contiguous areas of white pixels. I rewrote this algorithm in haskell.
The algorithm ...
4
votes
0answers
113 views
All the paths from the root to the leaves
Given a binary tree, return all root-to-leaf paths.
Example:
-- 1
/ \
2 3
\
5
Output should be: ["1->2->5", "1->3"]
My approach: I walk the branches ...
4
votes
0answers
151 views
Fast Hardy-Weinberg equilibrium simulation
I was very bored over one of my breaks this year, so I built a Hardy-Weinberg equilibrium simulator for two unrelated alleles of the same gene. Hardy-Weinberg equilibrium is when there is no evolution,...
4
votes
0answers
402 views
Parallel solutions to N Queens Puzzle
I'm trying to increase the performance of my N Queens Puzzle solution. I'd find some threads on SO already but they don't appear to help me to increase performance.
My best solution, however, is a ...
4
votes
0answers
2k views
Compression/decompression using Huffman Coding Algorithm
I am writing a program that compresses and decompresses data using the Huffman Coding algorithm.
About compression: this program will export 2 files: header file (contains characters' frequency for ...
4
votes
0answers
53 views
Time travelling through state history with persistent consequences
I am working on a game written in Kotlin that has a state management system similar to Redux. The state of the game is kept in a single place and is represented as immutable data classes (no logic). ...
4
votes
0answers
273 views
Linear Regression in Tensorflow
I am a machine learning newbie and recently I implemented (or at least tried to implement) a linear regression model in tensorflow. I would love to know how I can improve my code:
...
4
votes
0answers
137 views
Algorithm to find connected tiles (percolation)
I wrote a little program in JavaFX which displays a path of neighbouring open tiles going from top to bottom. It should simulate a percolation.
The algorithm iterates through the whole grid (every ...
4
votes
0answers
207 views
Finding where column slices of elements in multi-dimensional array are equal
Skippable Intro:
I have a dataset that corresponds to an observed time-series. The dataset is organized into a dictionary - which contains an array of years, an array of months, an array of days, an ...
4
votes
0answers
2k views
Reducing memory consumption for Numpy array
I'm running the following code using numpy arrays, I get a MemoryError in Ubuntu, while the same code runs on Mac OSX. (Pagination is automatically setup in Mac) This process consumes around 30 GB. ...
4
votes
0answers
58 views
Find spanning tree with maximum edges with the same weight
For my university assignment I need to come up with an algorithm to find a spanning tree with maximum number of edges with same weight. I received an algorithm suggestion in this Stack Overflow answer....
4
votes
0answers
895 views
Python code to calculate STM CRC32
I have code to calculate STM CRC32 in python. It works well but I'm shocked from time when I see how much it takes. Namely calculating for 5120 bytes takes about 20ms (or even more)! Now I'm thinking ...
