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.
344
questions with no upvoted or accepted answers
15
votes
0answers
183 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
46 views
Parallel merge sort with thread- and bufferpooling
I did wrote this parallel merge sort with no external dependencies. I tried to make use of modern C++ as much as possible.
Can you please tell me how it is?
...
8
votes
0answers
145 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
50 views
Fun crypto problem: Exploiting a vulnerable encryption scheme with Python
I came across a question asked here and here on the Crypto Stack Exchange site, and decided to analyze it as a kind of case study. To demonstrate the concept, I wrote a short python script depicting ...
7
votes
0answers
102 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 ...
6
votes
0answers
324 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
130 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
338 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
388 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
70 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
101 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 ...
5
votes
0answers
45 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
333 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
38 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
140 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 ...
5
votes
0answers
197 views
5
votes
0answers
73 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
6k 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 ...
5
votes
0answers
153 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:
...
4
votes
1answer
62 views
Maximum sub-array sum
My code finds the maximum subarray sum and the starting and ending index of that subarray.
...
4
votes
0answers
51 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
1answer
36 views
Calculate implicit dates
I need help to simplify this code about implicit date calculation.
The context: I have sentences with implicit and explicit dates. For instance:
"From the 5th to the 7th of September 2017, the ...
4
votes
0answers
93 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 I improve?
...
4
votes
0answers
58 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
89 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
56 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
0answers
65 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
79 views
Collatz Conjecture Disprover Unit - Googol Edition
The Wikipedia article about the Collatz Conjecture has these quotes:
If the conjecture is false, it can only be because there is some starting number which gives rise to a sequence that does not ...
4
votes
0answers
933 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
45 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
102 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
144 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
249 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
50 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
248 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
98 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
204 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
2k views
Implementation of the Householder Transformation
I implemented the Householder transformation in Python, so that I can later use it in a QR decomposition. Unfortunately I haven't found a good concise source for reading up on the algorithm.
I am not ...
4
votes
0answers
627 views
Minimum number of moves to solve “game of fifteen”
I read about this game and tried to make my own algorithm to solve this.
I asked it on StackOverflow for the appropriate algorithm and logic to solve this problem.
With the help of answers over ...
4
votes
0answers
1k views
Sanitize and standardize street addresses using Google Maps lookups
Take in incomplete user input street addresses, clean it, segregate based on word count and run it into Google maps places api and output completed & standardised addresses based on Json object ...
4
votes
0answers
2k views
Generic sliding window
The code implements fully generic sliding window with linear complexity. It should usually be paired with transforming iterator to reach full potential.
Sliding window is a grouping of elements by ...
4
votes
0answers
641 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 ...
4
votes
0answers
149 views
KMP algorithm searching from the right
The generic version of extension method is aimed to work like String.LastIndexOf which can search t from the last position of <...
4
votes
0answers
433 views
Hunt n' Kill algorithm
Last day I implemented the Hunt and Kill algorithm in JavaScript, using HTML5 without any libraries. I would like my code to be reviewed.
How it works
I start with a 2D array filled with walls (1-s),...
4
votes
0answers
2k views
Integer tree sort in Java
I have this algorithm for sorting integer arrays. Basically, it's a balanced tree sort which creates a tree node for each distinct integer, and in each tree node it maintains a counter counting how ...
4
votes
0answers
128 views
Refactored version of Okasaki's skew-binomial heaps in Standard ML
In his book, Purely Functional Data Structures, Chris Okasaki provides an implementation of skew-binomial heaps (p. 137). Unfortunately, the book isn't (legally) freely available anywhere, but his ...
4
votes
0answers
131 views
Heap update generic algorithms
In the standard library, there are no algorithms for element updates. This makes it unsuitable as a queue for a Dijkstra's algorithm, for example. Thus I implemented generic heap update functions with ...
4
votes
0answers
88 views
Minimum amount of edges that needs to be traversed to visit all vertices… or something like that
So I have this problem, where I'm given m connections over n vertices. The vertices are labeled ...
