Alexa Ryder

Graph Algorithms

Edmonds Karp Algorithm for maximum flow

Edmonds–Karp algorithm is an optimized implementation of the Ford–Fulkerson method for computing the maximum flow in a flow network in O(V E^2) time instead of O(E |max_flow|) in case of Ford-Fulkerson algorithm.

Graph Algorithms

Dinic's algorithm for Maximum flow in a graph

Dinic's algorithm or Dinitz's algorithm is a strongly polynomial algorithm for computing the maximum flow in a flow network. The basic principle is that a Maximum flow = minimum cut and Breadth First Search is used as a sub-routine.

Graph Algorithms

Ford Fulkerson Algorithm for Maximum flow in a graph

Ford–Fulkerson algorithm is a greedy algorithm that computes the maximum flow in a flow network. The main idea is to find valid flow paths until there is none left, and add them up. It uses Depth First Search as a sub-routine.

Graph Algorithms

Boruvka Minimum Spanning Tree

Borůvka's algorithm is an algorithm for finding a minimum spanning tree in a graph for which all edge weights are distinct, or a minimum spanning forest in the case of a graph that is not connected.

Graph Algorithms

Prim Minimum Spanning Tree Algorithm

Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. It finds a subset of the edges that forms a tree that includes every vertex,

Graph Algorithms

Kruskal Minimum Spanning Tree Algorithm

Kruskal's algorithm is a minimum-spanning-tree algorithm which finds an edge of the least possible weight that connects any two trees in the forest. It is a greedy algorithm in graph theory as it finds a minimum spanning tree for a connected weighted graph adding increasing cost arcs at each step

Graph Algorithms

What is a Minimum Spanning Tree?

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted directed or undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight.

Graph Algorithms

Shortest Path Faster Algorithm: Finding shortest path from a node

The Shortest Path Faster Algorithm (SPFA) is an improvement of the Bellman–Ford algorithm which computes single-source shortest paths in a weighted directed graph. The algorithm is believed to work well on random sparse graphs. SPFA Fanding Dung.

Graph Algorithms

Bellman-Ford Algorithm: Finding shortest path from a node

Bellman-Ford Algorithm is an algorithm for single source shortest path where edges can be negative (but if there is a cycle with negative weight, then this problem will be NP). The credit of Bellman-Ford Algorithm goes to Alfonso Shimbel, Richard Bellman, Lester Ford and Edward F. Moore.

Graph Algorithms

Floyd-Warshall Algorithm: Shortest path between all pair of nodes

Floyd-Warshall Algorithm is an algorithm based on dynamic programming technique to compute the shortest path between all pair of nodes in a graph. The credit of Floyd-Warshall Algorithm goes to Robert Floyd, Bernard Roy and Stephen Warshall.

Graph Algorithms

Dijkstra's algorithm: Finding shortest path between all nodes

Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a graph. Dijkstra's algorithm is applicable for: Both directed and undirected graphs, All edges must have nonnegative weights, Graph must be connected

Graph Algorithms

Breadth First Search

Breadth-first search (BFS) algorithm is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores along adjacent nodes and proceeds recursively.

Graph Algorithms

Fleury’s Algorithm: Finding Eulerian tours in a graph

Fleury's algorithm is a simple algorithm for finding Eulerian paths or tours. It proceeds by repeatedly removing edges from the graph in such way, that the graph remains Eulerian.

Graph Algorithms

What is a Euler or Eulerian tour?

An Euler tour or Eulerian tour in an undirected graph is a tour/ path that traverses each edge of the graph exactly once. Graphs that have an Euler tour are called Eulerian graphs.

Graph Algorithms

Find articulation points or cut vertices in a graph

Find articulation point or cut vertices in a graph. A vertex in an undirected connected graph is an articulation point or cut vertex if and only if removing it, and the edges connected to it, splits the graph into multiple components. Hint: Apply Depth First Search on a graph.

Graph Algorithms

Find cut edges in a graph

Find cut edges in a graph in linear time complexity using Depth First Search. A cut edge e = uv is an edge whose removal disconnects u from v. There are two key observations to solve this problem.

Graph Algorithms

Depth First Search

Depth-first search (DFS) algorithm is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.

Sorting Algorithms

Tree sort

Tree sort is an online sorting algorithm that builds a binary search tree from the elements to be sorted, and then traverses the tree (in-order) so that the elements come out in sorted order.

Sorting Algorithms

Shell Sort

Shellsort (also known as Shell sort or Shell's method) is an in-place comparison based sorting algorithm. Shell Sort improves its time complexity by taking the advantage of the fact that using Insertion Sort on a partially sorted array results in less number of moves.

Sorting Algorithms

Binary Insertion Sort

Binary search is used to reduce the number of comparisons in Insertion sort. This modification is known as Binary Insertion Sort. Binary Insertion Sort use binary search to find the proper location to insert the selected item at each iteration.

Sorting Algorithms

Insertion Sort

Insertion sort is an online stable in-place sorting algorithm that builds the final sorted list one item at a time. It works on the principle of moving a element to its correct position.

graph

Cheriton-Tarjan Minimum Spanning tree algorithm

The Cheriton-Tarjan algorithm is a modification of Kruskal's algorithm designed to reduce the O(e log e) term. Similar to Kruskal's algorithm, it grows a spanning forest, beginning with a forest of n = |G| components each consisting of a single node.

C++

Object Slicing in C++

Object slicing is a situation in `C++` when a derived class object is assigned to a base class object, the additional attributes of a derived class object are sliced off (not considered) to form the base class object. There are 3 key concepts involved.

Software Engineering

Implementing printf and scanf in C

Understanding how printf and scanf works internally is the key to writing advance code. Key concepts involved are variable number of arguments in functions using vararg in C. Use of internal buffer to prepare the input or output.

Sorting Algorithms

Merge Sort

Algorithm Pseudocode Visual Run Complexity Implementations Applications Reading time: 20 minutes | Coding time: 10 minutes The Merge Sort is an efficient comparison based sorting algorithm based on divide and conquer strategy. It has