- Algorithm tutorials
- Ramer–Douglas–Peucker algorithm: is an algorithm for reducing the number of points in a curve that is approximated by a series of points.
- PID controller: calculates an 'error' value as the difference between a measured [Input] and a desired setpoint. The controller attempts to minimize the error by adjusting [an Output].
- algorithm-cheat Algorithm tutorials and simple multi-language implementations with unit tests.
- Modified preorder tree traversal
- Answer with a list of implemented algorithms in well known softwares
- Image Quadrangulation
- Image Triangulation
- Image Triangulation: Voronoi Method
- Algorithms for sampling without replacement
- How a Kalman filter works, in pictures
- Floyd-Steinberg dithering
Bloom filters are space-efficient probablistic data structures used to test whether an element is a member of a set.
- Wikipedia entry
- Bloom filter calculator
- Bloom filters debunked: Dispelling 30 Years of bad math with Coq!
- When Bloom filters don't bloom
Channel coding&Error-correcting codes
- Reed-Solomon Codes
- Linear Feedback Shift Registers for the Uninitiated, Part XVI: Reed-Solomon Error Correction
- Cyclic Redundancy Check (CRC)
- Cyclic Redundancy Check: TMS320C64+ Implementation
- What Truncated polynomial mean in CRC16 CCITT context
- Best CRC Polynomials
- Brute forcing CRC parameters
- crcmod python module
- CRC Tool Kit
Time: \(\Omega(n^2)\) Space: \(\Omega(1)\)
It works by iterating over each element of the list, in order to find the smallest element to move in the needed position
Time: \(\Omega(n^2)\) or \(\Omega(n)\) Space: \(\Omega(1)\)
This works iterating over all elements for each entry ordering the ith element via insertion in the right position (practically implemented swapping). This has the property that at the ith step, the first i elements are ordered.
In general, insertion sort will write to the array \(\Omega(n^2)\) times, whereas selection sort will write only \(\Omega(n)\) times. For this reason selection sort may be preferable in cases where writing to memory is significantly more expensive than reading, such as with EEPROM or flash memory.
Time: \(\Omega(n\log(n))\) Space: \(\Omega(n)\)
This algorthm acts recursively: it works in two steps
- split in half the input and calls itself in each piece if length(piece) >= 4
when it merges, it builds the new piece taking the smallest element available between the two originals
Time: \(\Omega(n\log(n))\) Space: \(\Omega(\log n)\)
This is a divide and conquer algorithm that works in the following way
- picks a pivot element
reorders the elements so that