NOTIFICATION: These examples are provided for educational purposes. Using this code is under your own responsibility and risk. The code and information is given ‘as is’. I do not take responsibilities of how they are used.
List of Common Algorithms – Part 2 >
- Insertion sort: Efficient for sorting small number of elements. Remove one element at a time and insert it back into the correct position.
- Merge sort: Divide-and-conquer sorting algorithm. Divide the problem into small sub-problems. Solve the sub-problems recursively. Combine the solution of the sub-problems into the solution for the original problem.
- Bubble sort: Repeatedly swap adjacent elements in the right order.
- Horner’s polynomial rule: A rule which the number of necessary multiplications and results in less numerical instability due to potential subtraction of one large number from another are reduced.
- Permute-By-Sorting: Randomized algorithm in which the input is randomized by permuting the input array. This algorithm belong to the uniform random permutation algorithms.
- Randomize-In-Place: This algorithm belong to the uniform random permutation algorithm.
- Heapsort: Array in which elements can be viewed as a complete binary tree. Each node satisfy a heap property.
- Max-Heapify: subroutine for manipulating max-heaps. Normally used for Heapsort.
- Priority Queues: A set of data sequence in which each set of elements is associated with a value called key.
- Quicksort: Divide-and-conquer sorting algorithm. Uses a partition algorithm in order to divided the array.
- Random Sampling Quicksort: This version of the Quicksort algorithm performs a randomized-partition.
- Hoare partition: This version of the Quicksort algorithm performs a partition with the use of two indices in which each begins at the extreme ends of the input array.
- Stooge sort: Recursively sorting algorithm. Slower than Bubble sort.
- Stack Depth: Also known as tail recursion. After the partition, first sub-array to be recursively shorted will be the left sub-array, then the right sub-array.
- Median-of-3 partition: An improved version of the Randomized-Quicksort.
- Fuzzy sorting of intervals: Produce a permutation of the intervals such that the existent must satisfy a rule.
- Counting sort: For each input element, determine the number of elements less than the input. Assumes that the input consists of integers in a small range.
- Radix sort: Used for card-sorting. All cards are organized into 80 columns. In each column a card is punched into one of twelve places. Then a sort is perform on a list of seven 3-digit numbers.
- Bucket sort: Similar to counting sort however it assumes that the input is generated by a random process in which the numbers are distributed uniformly and independently over an interval [0,1).
- Randomized-Select: This algorithm only works on one side of the partition instead of both as in Quicksort. This algorithm uses a Randomized-Partition.
- Stacks: In a stack, the stack can implement a last-in, first-out (LIFO) policy or first-in, first-out (FIFO) policy.
- Queue: An stack with FIFO property which have a head and a tail.
- Enqueue: Insert operation on a queue.
- Dequeue: Delete operation on a queue.
- Linked-list: data structure in which each node is arranged in a linear order.
- Binary Tree: A parent node which have a left and right child node.
- Hash Tables: Generalization of a simpler notion of an ordinary array. It performs a direct addressing, applicable when allocating an array that has one position for every possible key is affordable.
- Direct-Address Tables: A dynamic set is represented by an array or direct-address table in which each slot (or position) correspond to a key.
- Open Addressing: Each table entry contain either an element of the dynamic set or none; therefore, we can say that all elements are being store in the hast table itself.
- Double Hashing: A method of open addressing in which permutations produced have randomly even permutations.
- Red-Black Trees: Binary tree in which each node have an extra bit of storage which is use to indicate the colour of the node: red or black.
- Matrix-chain multiplication: Compute the product of a given sequence (chain) of n number of matrices.
- Length of Less Common Denominator (LCS): Compute two sequences as input.
- Bitonic Euclidean Travelling-Salesman Problem: Also known as TSP. Algorithm that help to simplify the problem of determining the shortest closed tour that connects a set of given points.
- Viterbi Algorithm: Algorithm used for speech recognition. It help to solve a labelled graph made of a person speaking a restricted language.
- Greedy Algorithm: It is an algorithm in which the best looking choice is made at the moment.
- Fractional Knapsack Problem: Greedy algorithm for a problem related with items size, their price and storage.
- Huffman Algorithm: Algorithm use for compressing data in an effective way.
- B-Trees: Balanced search trees.
- Binomial trees: ordered tree defined recursively.
- Binomial heaps: Set of binomial trees which have binomial heap properties.
- Fibonacci heaps: Collection of min-heap-ordered trees.
- Unordered binomial tree: Binomial tree with a single node, and an unordered binomial tree consisted of two unordered binomial trees.
- Disjoint-set operations: Maintenance of a collection of disjoint dynamic sets.
- Disjoint-set forests: Set of rooted trees which in each of their nodes contain one member and each of these trees represent one set.
- Union by rank: Linked-list representation of the weighted-union heuristic.
- Path compression: simple and effective heuristic without changing any ranks.
- Union by rank with path compression: Combination of union-by-rank and path-compression heuristic.
- Off-line minimum problem: Maintenance of a dynamic set of elements from an specific domain.
- Adjacency-list representation: representation of a graph using adjacent list for each vertex.
List of Common Algorithms – Part 2 >
© 2011 – 2017, Alejandro G. Carlstein Ramos Mejia. All rights reserved.