Discover published sets by community

An algorithm for traversing or searching tree or graph data structures. It starts at the tree root and explores the neighbor nodes first, before moving to the next level neighbors. Complexity is O(V + E).

An efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item, until you've narrowed the possible locations to just one. The complexity is O(log n).

A subsequence of a given sequence in which the subsequence's elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous. Complexity is O(n log n) with a binary search approach.

The algorithm to find the largest possible flow in a flow network from a source to a sink. It's often solved using approaches like Ford-Fulkerson method or Edmonds-Karp algorithm. Complexity can be O(V^3E) with Ford-Fulkerson and O(VE^2) with Edmonds-Karp.

An algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. It works for both directed and undirected graphs with non-negative weights. The complexity is O((V+E) log V).

A best-first search algorithm that finds the shortest path from a given start node to a target node in a weighted graph with an admissible heuristic. Complexity typically is O(E), where E is the number of edges.

A string searching algorithm that finds the occurrence of a substring (the 'needle') within a main text string (the 'haystack'). It uses information gathered during the preprocess stage to skip sections of the text, resulting in a time complexity of O(n).

An algorithm that finds the maximum matching in a bipartite graph, which is a set of edges chosen in such a way that no two edges share an endpoint. Often implemented using the Ford-Fulkerson algorithm. Complexity is O(VE).

A simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. The algorithm's complexity is O(n^2).

A non-comparative integer sorting algorithm that sorts the data with integer keys by grouping keys by the individual digits which share the same significant position and value. Complexity can be as low as O(nk).

An in-place comparison sort which starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared. The worst-case time complexity is O(n^2).

A greedy algorithm that finds a minimum spanning tree for an additively weighted undirected graph. It finds the subset of edges that includes every vertex, where no cycle is formed, and is of minimum possible total edge weight. Complexity is O(E log E).

A string searching algorithm that searches for occurrences of a 'word' within a main 'text string' using the observation that when a mismatch occurs, the word itself embodies sufficient information to determine where the next match could begin. Complexity is O(n+m).

A classic computer science problem, the method to find the longest subsequence common to all sequences in a set of sequences (often just two). It is a problem closely related to the subproblems of edit distance. Complexity is O(nm).

An in-place comparison-based algorithm in which the list is divided into two parts, the sorted part at the left end and the unsorted part at the right end. Complexity is O(n^2).

A comparison-based sorting algorithm that uses a binary heap data structure. It starts by building a heap from the input data and then repeatedly extracts the maximum element from the heap. Complexity is O(n log n).

An algorithm to find the strongly connected components of a graph. It uses depth-first search to exploit the fact that the strongly connected components form subtrees of the DFS tree. Complexity is O(V+E).

An efficient method to compute the Greatest Common Divisor (GCD) of two numbers, which is the largest number that divides both of them without leaving a remainder. The algorithm runs in O(log min(a, b)).

A sorting algorithm that sorts the elements of an array by counting the number of occurrences of each unique element in the array. The complexity for this algorithm is O(n+k).

A sorting algorithm that distributes the elements of an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sort. Complexity is typically O(n+k).

A simple sorting algorithm that builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort. Complexity is O(n^2).

A dynamic programming algorithm that computes shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles). The algorithm complexity is O(V^3).

An algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph. It is slower than Dijkstra's but more versatile, as it can handle graphs in which some of the edge weights are negative numbers. Complexity is O(VE).

An algorithm for traversing or searching tree or graph data structures. It starts at the root and explores as far as possible along each branch before backtracking. Complexity is O(V + E).

A greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. The algorithm starts with a single vertex and keeps adding lowest-weight edges from those that connect the set of visited nodes to the set of unvisited nodes. Complexity is O(E log V).

A method for finding a target value within a list. It sequentially checks each element of the list until a match is found or the whole list has been searched. Complexity is O(n).

An efficient sorting algorithm that follows the divide and conquer approach. It picks an element as pivot and partitions the given array around the picked pivot. The average complexity is O(n log n).

An algorithm that finds a topological ordering of a directed graph. It provides a linear ordering of the vertices such that for every directed edge uv, vertex u comes before v in the ordering. Complexity is O(V+E).

A divide-and-conquer algorithm that divides the unsorted list into n sublists, each containing one element, then repeatedly merges these sublists to produce new sorted sublists until there is only one sublist remaining. Complexity is O(n log n).