String Searching Algorithm - Knuth Morris Pratt or KMP Algorithm
Posted on July 30, 2013
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
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]Priority Queue
Posted on July 30, 2013
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
What is priority queue?
A data structure for maintaining items or elements in a queue of priorities, which is usually implemented using an array. A queue of this nature helps to insert every item with an assigned priority and these inserted items could be deleted if required.
Minimum number of queues needed to implement the priority queue?
Two. One queue is used for actual storing of data and another for storing priorities.
[Read More]What is a non-linear datastructure?
Posted on July 30, 2013
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
A non-linear datastrucutre is a datastructure in which the data items in the memory are not allocated contiguously i.e. the data items are dispersed in the memory. The first data item will have a link to the second data item and second data item will have a link to the third data item and so on.
Pros
Uses memory efficiently that the free contiguous memory in not an requirement for allocating data items The length of the data items is not necessary to be known prior to allocation Cons
[Read More]What is a linear datastructure?
Posted on July 30, 2013
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Linear datastructure is one in which the data items are placed in the memory contiguously i.e. one after the other.
Pros
If we search the first data item, then it is very easy to find the next data items Cons
Size of the array must be know prior to allocation Requires contiguous memory, however if a free memory space is disjoint then this free memory space is not utilized for memory allocation Example of linear datastructure is an array.
[Read More]What is a sorting algorithm?
Posted on July 30, 2013
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
A sorting algorithm is an algorithm that sorts the data into ascending or descending order.
Examples of such sorting algorithms are:
Insertion sort
Posted on July 30, 2013
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
The sorting problem
Input: Array of numbers , unsorted. Eg.
Output : Same numbers sorted in some order, say increasing order. Eg.
Insertion sort:
An efficient elementary sort method which places each element in it’s proper place among the elements which are already placed
Pseudocode for selection sort
Starts by considering the first two elements of the array data, if out of order, swap them Consider the third element, insert it into the proper position among the first three elements.
[Read More]Introduction to Heap
Posted on July 30, 2013
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Definition of a heap
A heap is a data structure that contains objects which have comparable keys.
Uses of Heap
Some uses for a heap include: keeping track of employee records where the social security number is the key, network edges, events where there is a priority, etc.
Such a heap is called descending heap. In an ascending heap, on the other hand, the key value stored in a node is smaller than the keys of its children nodes.
[Read More]Selection Sort
Posted on July 30, 2013
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
The sorting problem
Input: Array of numbers , unsorted. Eg.
Output : Same numbers sorted in some order, say increasing order. Eg.
Selection Sort is a sorting algorithm that sorts data items into ascending or descending order, which comes under the category of in-place comparison sort.
Pseudocode of selection sort
Get the smallest element and put it in the first position Get the next smallest element and put it in the 2nd position ….
[Read More]What is Bucket Sort?
Posted on July 30, 2013
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
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]What is a Graph data structure?
Posted on July 30, 2013
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Graphs consist of 2 ingredients :
Vertices (V) , also called nodes and can be pictured as dots Edges (E) , the line connecting the nodes. Types of Graphs
Depending on the edges, there two types of graphs:
Undirected Graphs - A graph that entail edges with ordered pair of vertices, however it does not have direction define. Example of such a graph is the ‘Family tree of the Greek gods’ **Directed Graphs (**aka Arcs) - Directed Graph: A graph that entail edges with ordered pair of vertices and has direction indicated with an arrow.
[Read More]