CommonLounge is a community of learners who learn together. Get started with the featured resources above, ask questions and discuss related stuff with everyone.
Prim's algorithm for Minimum Spanning Tree
Given an undirected weighted graph, a minimum spanning tree (MST) is a subset of the edges of the graph which form a tree and have the minimum total edge weight. For a MST to exist, the graph must be connected (that is, every pair of nodes must be reachable from each other).
Example of Minimum Spanning Tree. Total edge weight ...
Dynamic programming is a fancy name for storing intermediate results and re-using the stored result instead of re-computing them each time.
Let's see an example of a dynamic programming problem. Once we solve the problem using dynamic programming, the formal technical definitions will be easier to follow.
Problem: You are given a grid of size n \times 2 and n tiles of size 2 \times 1. In how many different ways can you tile the grid such that the entire grid is covered and no tiles overlap. (The tiles look identical to each other. Two ways of tiling are different based on whether the tiles are placed horizontally or vertically).
Example: There are 3 possible ways of tiling a 3 \times 2 grid.
Yes. You can also use a set as a priority queue / heap, since a set supports strictly more functionality. I expect sets to be 2-5x slower than heaps / priority queues because it is maintaining a Balanced Binary Search Tree (BBST). 95% of the time, 2-5x slower doesn't matter.
Binary search: Video tutorial, code and extensions
Binary search is a method for quickly finding a specific target value in a sorted array. It begins by comparing the target value to the middle element of the array. Because the array is sorted, the comparison allows us to determine one-half of the array in which the target cannot lie. The search continues on the remaining half. By doing this repeatedly, we will eventually be left with a search space consisting of a single element, which would be the target value.
It's because if the array or list has the elements unsorted, then we need to sort it first. So the sort time complexity is O(nlogn) and then we use a binary search which takes O(logn). Overall it takes O(nlogn) for unsorted array or list.
If the array given is a sorted array then the search...