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

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

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

Stable Matching Problem Example

The Stable matching problem Example started with a question that, is that possible to design a college admission process that will be self enforcing? or a job recruiting process which is self enforcing? Stable Matching Wikipedia. Let’s say all Juniors in University started applying for summer Internships. The summer internship process is a two way … Read more