The Stack Overflow podcast is back! Listen to an interview with our new CEO.

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
Filter by
Sorted by
Tagged with
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

Spacial hashing Library

Old code ...
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 ...