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.

423 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
20
votes
0answers
364 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
156 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 ...
8
votes
1answer
212 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
427 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
71 views

Efficiently generate distinct subsets which sum to a particular value

Related: Find all distinct subsets that sum to a given number This code is supposed to efficiently generate all subsets of a list such that the subset's values sum to a particular target value. For ...
6
votes
0answers
626 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
144 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
216 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
8k 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
145 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
468 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
408 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
55 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
0answers
71 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
267 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
490 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
237 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
65 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
443 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
45 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
945 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 ...
5
votes
0answers
218 views

Spacial hashing Library

Old code ...
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
794 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
1answer
2k views

Hackerrank: Sherlock and anagram

Problem statement Given a string \$S\$, find the number of "unordered anagrammatic pairs" of substrings. Input Format First line contains \$T\$, the number of testcases. Each testcase ...
5
votes
0answers
163 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
242 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
762 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
75 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
79 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
280 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
139 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
71 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
3k views

Merge Two Sorted Lists in JavaScript

The task is taken from LeetCode Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists. Example 1: ...
4
votes
0answers
165 views

Find the starting indices of all occurrences of the pattern in the string - KMP algorithm follow-up

The task was initially solved here, but was too buggy: Given a string and a pattern, find the starting indices of all occurrences of the pattern in the string. For example, given the string "...
4
votes
0answers
252 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
565 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
98 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
101 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
2k views

Distance transform on image using NumPy

I would like to find the find the distance transform of a binary image in the fastest way possible without using the scipy function distance_transform_edt(). The ...
4
votes
0answers
47 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
114 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
152 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
482 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
3k 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
54 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
165 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 ...

1
2 3 4 5
9