## Minimum Spanning Tree

Let H = (V,T) be a subgraph of an undirected graph G = (V,E). H is a Minimum Spanning tree of G if H is both acyclic and connected and removal of edge disconnects it and the sum of the edge costs is minimized. Wikipedia Definition of Minimum Spanning Tree Here. Properties of Spanning Tree … Read more

## Dijkstra Algorithm Greedy Method

Dijkstra Algorithm Greedy Method is a greedy algorithm that solves the single-source shortest path problem for a directed graph G = (V, E) with nonnegative edge weights, i.e., w (u, v) ≥ 0 for each edge (u, v) ∈ E. For the Definition and more visit HERE Greedy Approach: Maintain a set of Explored Nodes S … Read more

## Optimal Caching – Greedy Algorithm

Optimal Caching is a technique that reduces the number of cache misses compared to any other method of cache management. There is a good course on Coursera about Greedy Algorithms Check it out HERE. Cache The cache is a small and fast memory. Cache process the sequence of “page requests”. Page requests are if a … Read more

## Scheduling to Minimize Maximum Lateness

The Definition of Scheduling to Minimize Maximum Lateness is “Given a set of n jobs all of which must be scheduled on a single resource such that all jobs arrive at time s and each job has a deadline di and a length ti, minimize the maximum lateness of the resulting schedule.” To read more visit HERE … Read more

## Interval Partitioning

When data put into a table surpasses all of the existing range partitions. Interval partitioning is an extension of range partitioning that directs the database to automatically build segments of a defined interval. At least one range division must be specified. For Definition and more visit HERE Example There are 10 Lectures, each with a … Read more

## Interval Scheduling Greedy Algorithm

The concept behind Interval Scheduling Greedy Algorithm is that we have a set of jobs (tasks) that need to be scheduled on a machine, and each job j has a start time Sj and a finish time Fj. We can’t schedule two jobs at the same time if they overlap. Our objective is to fill … Read more

## Which Sorting Algorithm is of Divide and Conquer Type

In a Divide and Conquer Paradigm we divide the bigger problem into smaller sub problems and call the function recursively to solve the sub problems. Divide and Conquer method is more appropriate for those problems that have polynomial time solutions. Some of the Divide and Conquer Algorithms are Insertion sort, bubble sort, etc. Read this … Read more

## Directed Acyclic Graphs Examples

In this post we are going to talk about Directed Acyclic Graphs Examples and Topological order in a graph. Directed Acyclic Graphs? Def. A Directed Acyclic Graph is is a directed Graph which contain no directed cycles. Definition of Directed Graphs HERE. Lemma. If a graph is Directed Acyclic then G has a node with no … Read more

## Strong Connectivity in Graphs

Strong Connectivity is a thing we use only in directed graphs. Definition of Directed Graphs HERE Def Nodes a and b in a graph are mutually reachable if there is both a path from a to b and also a path from b to a. If all the nodes in the graph are mutually reachable … Read more

## What is Big O Notation in Algorithm

Big O notation is a specific notation that indicates the speed of an algorithm. When you use others’ algorithms in your project it is necessary to calculate Big O notation. It will help you to know how fast or slow it will work in your case. To know more about Big O notation visit HERE Algorithm run-time at different rates Alex is working on a SpaceX search algorithm. When a rocket is poised to arrive on the Moon, his algorithm will kick in and assist in determining where to land. The Algorithm he has to use … Read more