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 ...
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...
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.
Quick-sort: Video tutorial, pseudo-code (and in-place sorting)
We want to sort an array with n elements. Quick-sort does this by breaking up the array into non-overlapping segments, sorting them separately and then combining the results.
For instance, suppose we have a box with slips of paper with numbers between 100 and 300 to be sorted. We could first separate the slips into two bunches: those with values below 200 and those with values above 200. We can sort these bunches separately. Since all the values in the second bunch are larger than those in the first bunch, we can combine them easily into a single sorted bunch. (See Sorting | Online Study Material - IARCS for a great resource on this.)
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.