Algorithms Definition

Algorithm is a set of precise instructions designed to solve a problem or perform a task. It's like a recipe, providing step-by-step guidance to achieve a desired outcome. Algorithms are used across many fields, from computer science to everyday problem-solving.

Paradigm

• Brute Force: look at all the possibilities and selects the best solution
• Greedy: choose the best option at the current time, without any consideration for the future
• Divide and Conquer - divide the problem into smaller parts and then solve those parts
• Dynamic Programming - build up a solution using previously found sub-solutions
• Backtracking - incrementally build candidates for a solution, but when the algorithm determines that a candidate cannot lead to a valid solution, it discards the candidate and backtracks to try another

Algorithm	Topic	Paradigm	Definition
Knapsack Problem	Set	Dynamic Programming	Optimize value by selecting items to fit into a limited-capacity knapsack
Articulation Points	Graph	Graph Theory	Identifies critical nodes whose removal would disconnect a graph
Bellman-Ford Algorithm	Graph	Dynamic Programming	Finds shortest paths from a single source to all other vertices in a weighted graph, even with negative edge weights. It works by repeatedly relaxing edges
Best Time To Buy Sell Stocks	Sliding Window / Set	Divide and Conquer	Problem of finding the maximum profit from buying and selling stocks at the right times
Binary Floating Point	Math	Floating Point Arithmetic	Representation of real numbers in binary format with a floating-point
Binary Search	Search	Divide and Conquer	Search algorithm that divides a sorted array into halves, eliminating half of the remaining elements in each step.
Bit Manipulation	Math	Bitwise Manipulation	Manipulating individual bits within binary numbers
Breadth-First Search (BFS)	Graph / Tree	Graph Traversal	Traversal algorithm that systematically explores all neighbor nodes at the present depth prior to moving on to nodes at the next depth level
Bridges	Graph	Graph Theory	Edges in a graph, the removal of which would increase the number of connected components
Bubble Sort	Sort	Comparison-based Sort	A simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order
Bucket Sort	Sort	Distribution-based Sort	A sorting algorithm that distributes elements into a number of "buckets", and then sorts each bucket individually
Caesar Cipher	Cryptography	Substitution Cipher	A substitution cipher that shifts characters in the alphabet by a fixed number of positions
Cartesian Product	Set	Combinatorial	Set of all possible ordered pairs from two sets
Combination Sum	Combinatorial Problem	Backtracking	Finding combinations of numbers that sum up to a given target value
Combinations	Set	Divide and Conquer	Selections of elements without considering the order
Complex Number	Math	Mathematical	A number that comprises a real part and an imaginary part
Counting Sort	Sort	Sort	A non-comparison-based sorting algorithm that sorts elements by counting the number of occurrences of each unique element
Depth-First Search (DFS)	Graph / Tree	Divide and Conquer	Traversal algorithm that explores all neighbor nodes at the present depth prior to moving on to nodes at the next depth level
Detect Graph Cycle	Graph	Graph	Algorithms used to determine if a graph contains a cycle
Dijkstra Algorithm	Graph	Greedy	Algorithm used to find the shortest paths from a single source node to all other nodes in a weighted graph
Discrete Fourier Transform	Math	Brute Force	Transforming discrete data from the time domain to the frequency domain
Euclidean Algorithm	Math	Divide and Conquer	Finding the greatest common divisor of two integers
Euclidean Distance	Math	Mathematical	The distance between two points in Euclidean space
Eulerian Path and Eulerian Circuit - Fleury's Algorithm	Graph	Graph	Algorithms used to find paths and circuits that traverse each edge of a graph exactly once
Factorial	Math	Mathematical	The product of all positive integers up to a given number
Fast Powering	Math	Divide and Conquer	Efficiently computing the exponentiation of a number
Fibonacci Number	Math	Dynamic Programming	A sequence of numbers where each number is the sum of the two preceding ones
Fisher–Yates Shuffle	Set	Randomization	A method for randomly shuffling the elements of an array
Floyd-Warshall Algorithm	Graph	Dynamic Programming	Algorithm used to find the shortest paths between all pairs of nodes in a weighted graph
Hamiltonian Cycle	Graph	Backtracking	A cycle that visits each vertex of a graph exactly once
Hamming Distance	String	Mathematical	The number of positions at which corresponding symbols differ in two sequences
Heap Sort	Sort	Sort	A sorting algorithm that utilizes the heap data structure to sort elements in ascending or descending order
Hill Cipher	Cryptography	Cryptography	A polygraphic substitution cipher based on linear algebra
Horner's Method	Math	Mathematical	An algorithm for polynomial evaluation
Insertion Sort	Sort	Sort	A sorting algorithm that builds a sorted list one element at a time by repeatedly inserting the next element into the already sorted part of the list
Integer Partition	Math	Dynamic Programming	Representing a given integer as the sum of other integers
Interpolation Search	Search	Search	A search algorithm that extrapolates the position of the target value based on its value and the values of the array's endpoints, providing a quicker approach for uniformly distributed data
Is Power of Two	Math	Math	Determining whether a given integer is a power of two
Jump Game	Array	Backtracking / Divide and Conquer / Dynamic Programming / Greedy	Problem of determining if it's possible to reach the last index of an array starting from the first index
Jump Search (or Block Search)	Search	Search	An algorithm that jumps ahead by fixed steps and then performs linear search within the block until the desired element is found
k-Means	Machine Learning	Clustering	A clustering algorithm that partitions data into k clusters based on similarities
k-NN	Machine Learning	Machine Learning	k-Nearest Neighbors, a non-parametric method used for classification and regression
Knight's Tour	Graph	Backtracking	Problem of finding a sequence of moves for a knight on a chessboard that visits every square exactly once
Knuth–Morris–Pratt Algorithm (KMP Algorithm)	String	String Matching	An efficient string-searching algorithm that searches for occurrences of a "word" within a larger "text"
Kruskal's Algorithm	Graph	Greedy	Greedy algorithm used to find the minimum spanning tree of a connected, undirected graph
Least Common Multiple (lcm)	Math	Mathematical	The smallest positive integer that is divisible by two given integers
Levenshtein Distance	String	Dynamic Programming	The minimum number of single-character edits (insertions, deletions, or substitutions) required to change one word into another
Linear Search	Search	Brute Force	A basic searching algorithm that sequentially examines each element in a list until a match is found
Liu Hui π Algorithm	Math	Mathematical	A method for approximating the value of π
Longest Common Subsequence (LCS)	Set	Dynamic Programming	The longest sequence that is common to two or more sequences
Longest Common Substring (LCS)	String	Dynamic Programming	The longest sequence of characters that appears in both given strings
Longest Increasing Subsequence (LIS)	Set	Dynamic Programming	The longest subsequence where elements are in increasing order
Matrices	Math	Divide and Conquer	Rectangular arrays of numbers
Maximum Subarray	Array	Brute Force / Divide and Conquer / Dynamic Programming	Problem of finding the contiguous subarray with the largest sum within a given array
Merge Sort	Sort	Divide and Conquer	A divide-and-conquer sorting algorithm that recursively divides the input list into smaller sublists, sorts those sublists, and then merges them back together
N-Queens Problem	Array	Backtracking	Problem of placing N queens on an NxN chessboard such that no two queens attack each other
NanoNeuron	Machine Learning	Machine Learning	A simplified model of a neuron used for educational purposes in machine learning
Palindrome	String	String Manipulation	A sequence that reads the same backward as forward
Pascal's Triangle	Math	Divide and Conquer	A triangular array of binomial coefficients
Permutations	Set	Divide and Conquer	Arrangements of elements in a specific order
Polynomial Hash	Cryptography	Hash	A hash function that converts a string into a polynomial representation for efficient hashing
Power Set	Set	Backtracking	Set of all subsets of a given set
Primality Test	Math	Mathematical	Determining whether a given number is prime or composite
Prime Factors	Math	Mathematical	The prime numbers that multiply together to give a composite number
Prim's Algorithm	Graph	Greedy	Greedy algorithm used to find the minimum spanning tree of a connected, undirected graph
Quicksort	Sort	Divide and Conquer	A divide-and-conquer sorting algorithm that partitions the input list into smaller sublists, recursively sorts those sublists, and then combines them
Rabin Karp Algorithm	String	String Manipulation	A string-searching algorithm that searches for patterns in a string using hashing
Radian & Degree	Math	Mathematical	Units of measurement for angles
Radix Sort	Sort	Sort	A non-comparison-based sorting algorithm that sorts elements by their digits or numbers
Rail Fence Cipher	Cryptography	Cryptography	A transposition cipher that encrypts and decrypts messages by shifting characters along diagonal rails
Rain Terraces	Array	Brute Force / Dynamic Programming	Problem involving calculating the amount of water that can be trapped between blocks
Recursive Staircase	Math	Brute Force / Dynamic Programming	Problem of counting the number of ways to climb a staircase with a given number of steps
Regular Expression Matching	String	Dynamic Programming	Determining if a string matches a pattern specified by a regular expression
Reverse Traversal	Linked List	Iteration	Traversing elements in the reverse order of their appearance in a data structure
Seam Carving	Image Processing	Dynamic Programming	An image resizing technique that removes or adds pixels in a way that preserves the most important features of the image
Selection Sort	Sort	Sort	A sorting algorithm that divides the input list into two parts: a sorted sublist and an unsorted sublist, and repeatedly selects the smallest (or largest) element from the unsorted sublist to add to the sorted sublist
Shell Sort	Sort	Sort	A variation of insertion sort that sorts elements at different intervals to improve performance
Shortest Common Supersequence (SCS)	Set	Dynamic Programming	The shortest string containing both given strings as subsequences
Sieve of Eratosthenes	Math	Prime Number	An algorithm to find all prime numbers up to a specified integer
Square Root - Newton's method	Math	Math	An iterative method for finding square roots
Straight Traversal	Linked List	Iteration	Traversing elements in the order they appear in a data structure
Strongly Connected Components - Kosaraju's Algorithm	Graph	Graph	Algorithms used to find sets of vertices in a directed graph such that every vertex in the set is reachable from every other vertex
Topological Sorting	Graph	Graph	Arranging the nodes of a directed graph in a linear order respecting the dependencies between nodes
Tower of Hanoi	Math	Divide and Conquer / Recursion	Mathematical puzzle involving the movement of disks from one peg to another, following certain rules
Travelling Salesman Problem	Graph	Brute Force	A problem that asks for the shortest possible route that visits each city exactly once and returns to the origin city
Unbound Knapsack Problem	Set	Dynamic Programming / Greedy	Variation of the knapsack problem where there is an unlimited supply of each item
Unique Paths	Grid	Backtracking / Dynamic Programming	Problem of counting the number of unique paths from the top-left corner to the bottom-right corner of a grid
Weighted Random	Statistics	Randomization	Generating random values with different probabilities assigned to each value
Z Algorithm	String	String Matching	substring search (pattern matching)