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.
5,095 questions
4
votes
0
answers
47
views
SHA1 Algorithm Implementation in Zig
I have implemented the SHA1 algorithm in Zig, as a learning exercise, to teach myself both Zig and the actual algorithm behind SHA1. Now the second part I think I understood well enough. The ...
9
votes
5
answers
2k
views
C method to determine whether a byte array is homogeneous
I engineered myself into a situation where I wanted to check whether a region of memory consists of identical bytes. I wanted to at least try to avoid the obvious solution of an O(n) loop, but also ...
5
votes
2
answers
75
views
Calculate distance score for local alignments (ex. Gotoh local)
Is there a better way to calculate distance scores for local alignment than this? Or is the method that I'm currently using robust enough? The full code is here with the actual alignment ...
4
votes
2
answers
222
views
Ruby Array#own_shuffle method
I have tried to implement the Array-shuffle method myself. Haven't had a look on some similar algorithm-examples by purpose and tried to figure out something myself.
The actual Array-extension:
...
7
votes
3
answers
525
views
Team picker command line application
I've made a program for randomly splitting game participants into different teams. The code works and solves the problem. I'm interested in advice on what you'd do differently or better.
...
5
votes
2
answers
131
views
N-dimensional bilateral_filter Template Function Implementation for Image in C++
This is a follow-up question for An Updated Multi-dimensional Image Data Structure with Variadic Template Functions in C++ and bilateral_filter Template Function Implementation for Image in C++. The N-...
2
votes
1
answer
156
views
Attempt at a Different Variation of the strstr(...) Function
I decided to work on an idea I had to 'optimize' the classic C function strstr.
Most of the implementations I had seen that did not make use of advanced ...
7
votes
2
answers
514
views
Subtracting the sum of the current digits from a positive integer N until it reaches 0
Given a positive integer N, subtract the sum of its digits and count how many times this operation must be applied to make N become 0.
...
3
votes
1
answer
59
views
More shortest unrestricted paths to touch every square in an n by n grid
This is a part two.
The problem originates from here,
it is solved for \$n<11\$. A GitHub repository for this code, printing paths, and a collection of all proven best paths, it is open to ...
5
votes
4
answers
598
views
Single Consumer Single Producer Wait-Free Zero-Copy Circular Message Queue
The title describes pretty well what the algorithm is for. It will be used for a realtime inter-process communication library that only uses shared memory for exchanging data. For realtime systems, it'...
4
votes
3
answers
542
views
Finding Special Parts in a Word
Task description:
Imagine you have a long word made up of small letters like "a", "b", "c", ancd so on. Let’s call this word a puzzle word.
We want to look at all the ...
4
votes
1
answer
103
views
Efficient way to win points in chocolate bowl game
I'm working on an optimization problem involving a turn-based chocolate-sharing game, and I need help optimizing my current brute-force solution.
Problem Description:
You and your friend take turns ...
2
votes
0
answers
89
views
backward induction algorithm computation
Is there a way to significantly speed-up this code?
I'm solving a dynamic programming model using a backward induction algorithm. A crucial step is to calculate the current-period value function (VF), ...
7
votes
1
answer
216
views
bilateral_filter Template Function Implementation for Image in C++
This is a follow-up question for An Updated Multi-dimensional Image Data Structure with Variadic Template Functions in C++. Bilateral filter is implemented in this post. By Wikipedia, the bilateral ...
2
votes
0
answers
142
views
How to make this arbitrary precision π calculator using Machin-like formula run faster?
Two days ago (or yesterday depending on your timezone) was π-day. So I thought it was a good day to calculate π.
I used Machin-like formula to calculate π, in homage of William Shanks, who calculated ...
5
votes
4
answers
505
views
Count number of substrings in less time
Given an input string contains letters from 'a' to 'g'
Count how many substrings are there in the input string such that
frequency of any character inside the substring is not more than the
number of ...
4
votes
1
answer
138
views
otsu_threshold Template Function Implementation for Image in C++
This is a follow-up question for An Updated Multi-dimensional Image Data Structure with Variadic Template Functions in C++, histogram Template Function Implementation for Image in C++, Histogram of ...
4
votes
2
answers
524
views
Simple Java program to aggregate lines of a text file
I have just written a small application to aggregate the lines of a text file, for example to group the lines according to the frequency of IP addresses in a log file.
Would the code be sufficiently ...
6
votes
3
answers
788
views
Collision detection of two rects with rounded borders
I wrote an algorithm how to detect the collision detection of two rects with rounded borders (the code was written using TypeScript but I tried to name things as clear as possible to code be readable ...
3
votes
1
answer
83
views
Depth-first ListIterator over JTree
I wrote a depth-first ListIterator for JTrees.
Considerations:
It must be a ListIterator, ...
13
votes
5
answers
2k
views
solve n*m matrix processing in less time
I want to solve a problem in less time complexity. Here are the details:
Given an n*m matrix, n rows and m columns. Initially, the matrix is empty filled with 0s.
...
9
votes
4
answers
2k
views
"Weird Algorithm" (Collatz) from CSES Problem Set
I had to solve the following problem:
Consider an algorithm that takes as input a positive integer n. If n is even, the algorithm divides it by two, and if n is odd, the algorithm multiplies it by ...
3
votes
1
answer
146
views
Fuzzy search in C#
I was asked to implement a FuzzySearch class in a C# project with the ability to change the degree of fuzziness.
It is to be used in a clinical setting where we get names with different linguistic ...
4
votes
1
answer
100
views
Swift Arrays: Write a rotate-right function
Task:
Write a function which rotates all elements of a given array to the right.
Example: [1, 2, 3] => [3, 1, 2]
My solution:
...
7
votes
4
answers
485
views
Traversal Heap Sort (No Extractions)
I developed a heap sort variant that sorts a heap through traversal. Unlike in the standard heap sort, the algorithm does not remove the min element from the heap instead it traverses all the nodes of ...
5
votes
2
answers
962
views
LeetCode 3366: Minimum Array Sum - w/o DP/memoisation
This program tried to solve LeetCode problem 3366: Minimum Array Sum.
It fails for k odd, op1+op2 high enough such there are more odd value to optionally subtract k from than subtractions to allot.
A ...
8
votes
1
answer
240
views
TF-IDF Implementation in Java
I have tried following the formulas for Term frequency–Inverse document frequency (TF-IDF) calculation and Cosine similarity calculation, and translated it into code. The results I get seems to be ...
4
votes
2
answers
119
views
Polynomial.java - multiplication algorithms: naïve, Karatsuba, FFT
Intro
This post is a supplement to Polynomial.java - a Java class for dealing with polynomials with BigDecimal coefficients. It presents the three polynomial multiplication algorithms. Given two ...
5
votes
1
answer
182
views
Code to generate an array of 364 random special characters with 20 random words broken up throughout
I am trying to recreate a Fallout 4 style terminal hacking game, so I wanted to create code to generate the terminal output (namely, 32 rows with 12 characters each and 20 random words spread out). ...
2
votes
0
answers
52
views
Brzozowski Algebraic Method for converting finite automaton from NFA to DFA
The Brzozowski Algebraic Method is a technique used in automata theory, specifically for constructing the minimal deterministic finite automaton (DFA) from a given nondeterministic finite automaton (...
-4
votes
1
answer
96
views
Pyramidal (Heap) sorting by D. Knuth
Help me with Pyramidal sorting by D. Knuth algorithm in C++.
I would like to clarify if I followed the algorithm correctly.
The code works.
I have the function, but I'm not sure if my code fully ...
3
votes
1
answer
177
views
Getting all column vs. table regardless of alias using JSqlParser
I have been trying to get all column vs. table regardless of alias used, for example, assume this query
...
3
votes
1
answer
91
views
Merge discrete integer intervals
What it does
The code starts with a set of integer intervals, and can add new intervals (possibly by updating existing intervals). Essentially, it is a bit array whose index starts at ...
2
votes
1
answer
222
views
Pattern search algorithm for infinite integer string in R
Let X = "1234567891011..." the infinite string contains all positive integers. str is a sequence of digits. We are asked to find the first location in X that str appears.
I have tried the ...
9
votes
3
answers
2k
views
Is set of integers closed under the operation of subtraction?
I was working on a problem, but my solution did not pass the time limit test.
Problem
Let's say a set of integers is closed under the operation of
subtraction if for two distinct elements of this set ...
4
votes
2
answers
159
views
Basic Linked List Implementation in JavaScript
Clarification of Intent
Recursion here is used on purpose for practice - note that iteration is preferred in this case (I'll be more clear about where my intentions are!)
Factory function was also ...
3
votes
1
answer
82
views
<Programming in Lua - 4th> exercise 2.2 - place 8 queens
About exercise 2.2
Place N queens on N*N board, 1 queen per line, so that all queens are safe.
Use permutation to improve the provided implementation from book.
The ...
5
votes
3
answers
1k
views
Coding exercise to represent an integer as words using python
Context:
Convert a non-negative integer num to its English words representation.
Example 1:
Input: num = 123
Output: "One Hundred Twenty Three"
Example 2:
Input: num = 12345
Output: "...
8
votes
2
answers
337
views
Determining Error Rate of Phase Shift Keying via Monte Carlo Simulation
My program calculates the symbol error rate for various signal-to-noise ratio (SNR) and modulation orders using Monte Carlo simulation on Phase Shift Keying (PSK). How can it be improved?
...
2
votes
3
answers
198
views
Efficiently tagging first and last of each object matching condition
How can I make the code more readable and more efficient? (provided code is O(n²) time, but intuition says it can be pre-processed and done in O(n) time)
Description
it tags the first and last of ...
2
votes
1
answer
91
views
Check which sinks are connected in the pipe system using Python
It would be very helpful to me as a beginner if I could get feedback on my code, specifically about the efficiency of algorithm used and potential improvements in code quality.
Code context:
There is ...
5
votes
4
answers
1k
views
Fast circular buffer [closed]
I'm working on a modern C++20 solution that does two things:
It accumulates a sliding window of input data points; the sliding window's size is fixed and known beforehand. Data has strict ordering ...
4
votes
1
answer
135
views
Advanced Python Calculator using OOP
I've been into computer science fundamentals (proper data structures/algorithms/etc) including Object Oriented Programming. Therefore, I decided to reformat my old traditional Python Calculator into ...
7
votes
3
answers
762
views
Optimal Algorithm to Append and Access Tree Data
I have been studying intermediate or more advanced data structures in Python, one of which I've decided to try out is the Tree Data Structure. I've been studying the theories as well as the ...
2
votes
1
answer
216
views
Pollard's rho algorithm implementation
I used std::multiset to determine how many times that factor appears.
I'd like to know if it can be improved; I've focused on the algorithm rather than the code.
...
2
votes
1
answer
104
views
What is the most efficient way to figure out if a single number is prime for numbers from 2 up to 2,147,483,647 in Java?
As Java programmers, we can always use the BigInteger isProbablePrime() method or store manually all prime numbers in a HashMap. This question is about the most efficient way to figure out if a single ...
4
votes
1
answer
140
views
Efficient polynomial multiplication in Python
I'm practicing problems for the ICPC competition, and one of the problems requires solving it by using an FFT to compute the product of two polynomials efficiently. Since this is for the ICPC ...
3
votes
2
answers
726
views
More Square Root
This is a follow up question to my Studies on Square Roots post. I'm posting additional code for solving for square root similar to the other, but with more code to benchmark.
...
8
votes
4
answers
962
views
Studies on Square Roots
This post marks the beginning of my ventures into calculating square roots. However, I have no idea how the processor, more specifically the FPU with the fsqrt ...
1
vote
2
answers
116
views
A simple performant factorial function
I am new to algorithm and data structure. After a little introduction to the topic, I have decided to implement a function called calculateFactorial, which takes an integer and calculates its ...