References
http://www.durofy.com/computing/linear-search-in-c/
Linear Search on Array
Posted on August 7, 2013 (Last modified on August 7, 2020) | 1 minutes | Kinshuk Chandra
Linear Search on Array
Topological Sorting
Definition
Topological sort: an ordering of the vertices in a directed acyclic graph, such that: If there is a path from u to v, then v appears after u in the ordering.
A topological ordering of a directed graph G is a labeling f of G’s nodes (1…n) such that:
(1) the f(v)’s are the set {1, 2, … , n}
(2) if (u, v) in G, then f(u) < f(v) … the graph should move in forward direction.
[Read More]
Dijkstra's Shortest Path Algorithm
It’s Dijkstra’s algorithm, that lets you find single-source shortest paths.
Problem
Problem - Single source shortest paths
Input -
Directed graph G=(V,E) Source vertex s Output - foreach v∈V, compute L(v)=length of a shortest s-v path in G.
Assumptions:
There is a path from vertex s to vertex v (otherwise, the path length is infinity) Edge lengths are non-negative (there are other algorithms for this called , but most famous being Bellman ford algorithm which uses dynamic programming) Example of shortest path
[Read More]
Graph Search Introduction
Graph search algorithms are important but lets have some motivations.
Motivation behind graph search
Here are few motivations:
Minimal Road network - Are there sufficient roads for people to go from one place to another. Imagine, Haridwar is only connected via Delhi and there is a natural calamity, then one way people can reach there for relief etc is via Delhi, resulting in worst disaster management, but suppose it is connected via many places, sending relief will be easier.
[Read More]
String Searching Algorithm - Knuth Morris Pratt or KMP Algorithm
Knuth-Morris-Pratt string searching algorithm:
- This algorithm searches a word->w within the main string text->s
- Such a search must employ the following observation:
i) A given match determines where the next match could begin
ii) The above intelligence is obtained for the search word itself that contains sufficient information for making such a discussion (i.e. determine where the next match begins)
Advantage of this string searching algorithm: Helps to avoid the re-examination of already matched characters
[Read More]
What is Bucket Sort?
Bucket Sort (alternatively know as bin sort) is an algorithm that sorts numbers and comes under the category of distribution sort.
This sorting algorithm doesn’t compare the numbers but distributes them, it works as follows:
Partition a given array into a number of buckets One-by-one the numbers in the array are placed in the designated bucket Now, only sort the bucket that bare numbers by recursively applying this Bucket Sorting algorithm Now, visiting the buckets in order, the numbers should be sorted Java code:
[Read More]
Binary tree traversal: Preorder, Inorder, Post-order, BFS, DFS, Level Order, zig zag order
In order to illustrate the 3 traversals - pre order, in-order and post-order lets take following tree:
Preorder traversal:
To traverse a binary tree in Preorder, following operations are carried-out (i) Visit the root, (ii) Traverse the left subtree, and (iii) Traverse the right subtree.
Therefore, the Preorder traversal of the above tree will outputs:
7, 1, 0, 3, 2, 5, 4, 6, 9, 8, 10
Implementing pre-order traversal
[Read More]
Circular Stack
There is no diffeence in circular list stack and non circular list stack. The insertion, deletion operation takes place in the same place. So it won’t create any modification in the circular list.
Here is the implementation of circular stack in CPP
Program in cpp
#include <iostream.h> #include <stdlib.h> using namespace std; struct node { int info; struct node \*next; }; int c=0; struct node \*top;int empty() { return((top == NULL)?
[Read More]
Red Black Tree – Insertion
Introduction:
Please refer the introduction of RBT here. So, we now know the invariants or properties of RBT which make it rbt :)
Insertion of element in RBT or red black tree breaks one of the 4 invariants or properties. So we have to fix it in minimal possible way. To assist us with we have 2 solutions :
Flipping the color Right and left rotation Insertion:
Insertion begins by adding the node much as binary search tree insertion does and by coloring it red.
[Read More]
Bloom filters
The bloom filter is a data structure designed in 1970. It is similar to a hash table. They are more efficient than a hash table, but they do raise false positives at times.
Supported Operations
A bloom filter supports super fast lookup and insertion, just like a hash table. So why have this data structure?
Pros
It is much more space efficient.
It takes the space even less than that of the object.
[Read More]