Single Source Shortest Path Problem: For a given directed graph G and a starting vertex v, find the shortest weighted path to all the vertices in G starting from v. Relaxing an edge Relaxation is a technique of minimizing the distance by updating distance to a vertex if another adjacent vertex is found so...
Spanning Tree is a subgraph (which is also tree) of a undirected connected graph that connects all the vertices of the given graph. Weight of a spanning tree is the sum total of the weights of all the edges spanning tree. Minimum Spanning Tree...
Depth-first search explores all vertices starting with source vertex in following manner: explore all unexplored edges leaving from most recently discovered vertex once all edges from a vertex are explored then backtrack to the vertex from which was discovered and explore its remaining edges...
Description Given an array of n elements, find largest sub-sequence in which elements are in sorted order. Assumption Desired sub-sequence does not have to be contiguous. Solution – Dynamic Programming Dynamic Programming can be used to solve this problem in time. Lets assume, be...
Description Given n types of coin denominations of values , make change for an amount of money C with as few coins as possible. Assumption Assume change for any amount C can always be made Solution Similarity with Knapsack Problem Optimal way to make...
Description Given a set of n real numbers , determine a contiguous sub-sequence for which sum of elements in sub-sequence is maximized. Solution Consider all the possible sums of elements of all sub-arrays ending in position j. Let be the maximum sum of all...
Description Given a set of items, each with a weight and a value, determine the count of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as...
BFS searches explores all the edges to discover all the vertices reachable from a given vertex. It computes minimum distance from s to all reachable vertices It produces a breadth-first tree with root s and containing all the vertices reachable from s It is...
Heap Data Structure Heap is an almost complete Binary Tree in which element at every node is greater (in case of min-heap its smaller) than both its children node (right and left nodes) elements. As a corollary, root of a heap is always the...
Finding Maximum and Minimum Finding a maximum or minimum in a set of n elements takes comparisons = Finding Minimum and Maximum at same time Calculating min and max individually takes comparisons in total. This can be improved by calculating min and max both...