DFS (Depth first search) for graph

 Posted on August 25, 2013  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

What is dfs? This algorithm explores aggressively and backtracks only when necessary. This is similar to how we play a maze game. To code DFS iteratively, we can mimic BFS , but use a Stack instead of a Queue. Another way to code this would be to do it recursively. DFS is very naturally phased as recursive example. We will see both of implementation later. DFS(graph G, vertex s) mark s as explored for every edge (s, v): if v unexplored DFS(G, v) Example : Consider the graph: [Read More]
Graph  kodeknight  time complexity  DFS  graph-search 

Dijkstra's algorithm for equal weight edges using BFS

 Posted on August 25, 2013  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

This is the application of BFS (breadth first search) dist(v) = fewest number of edges on path s to v. Here is the pseudocode: Initialize dist(v) = {0 if v=s, infinity if v != s} foreach vertex v in all vertices { if(v==s) dist(v) = 0; else dist(v) = infinity; } Now apply BFS, and hen considering edge (v, w), if w is unexplored, then set dist(w) = dist(v)+1, keeping rest of the BFS same. [Read More]
Graph  kodeknight  BFS  graph-search 

Deleting the element from the heap

 Posted on August 24, 2013  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Here we will discuss deletion of element from min heap. Pseudocode for deletion from heap Find the index of the element to be deleted from the heap. This takes O(n) time.(If you already have the index, please skip this step) Remove the element from the heap Move the root element to the element to be deleted location Move the last element to the first position Decrease array size by 1 Now bubble down on the array(like we did in extract min). [Read More]
kodeknight  heap 

Application of heap (in computer science)

 Posted on August 24, 2013  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Following are applications of heap: Heap Sort - fast way to get minimum computation SelectionSort() with time complexity - Θ(n2) when uses heap data-structure is used as Heapsort, with time compexity nlogn. Heapsort has 2 steps Insert all n array elements in the heap O(n) Extract min to place elements in sorted order n * O(lg n) So, it is now close to quicksort. Priority Queue [Read More]
kodeknight  heap 

Building of heap

 Posted on August 24, 2013  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

To be done soon.

kodeknight  heap 

Array Implementation of Heap

 Posted on August 24, 2013  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

The parent function seems to be a bit in-correct. …

Anonymous - Apr 3, 2014

The parent function seems to be a bit in-correct. It should return i/2 if i is even.
parent(i)
{
if(i is even)
return i/2;
else
return floor(i/2);
}

Thanks mate for the correction. I have corrected it.

kodeknight  array  heap  Data Structure 

Array Implementation of Heap

 Posted on August 24, 2013  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

We have discussed a heap as binary tree. Normal implementation of tree is via pointer, but in heap it is much more efficient to use arrays. So, suppose we have following heap (having 9 elements) : Now, we need array of 9 elements. Now, we see the heap having 3 levels, level 0 as root, and level 3 which is partially filled. Now, we start putting the elements one by one. [Read More]
kodeknight  array  heap  Data Structure 

Find Nth largest element in the rotated sorted array

 Posted on August 24, 2013  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Please give review to this post http://rawjava.blo…

Unknown - Apr 1, 2015

Please give review to this post
http://rawjava.blogspot.com/2015/04/java-program-to-find-maximum-number.html

Good question and equally good answer..Enjoyed your post :)

search  ArraySearch  kodeknight  recursion  array  binary search  rotated array  kth-largest  min  sorted-array 

Find Nth largest element in the rotated sorted array

 Posted on August 24, 2013  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

**Question : **Find Nth largest element in the rotated sorted array So for example we have sorted array as - 2,3,6,12, 15, 18. Now suppose the array is rotated k times ( we don’t know k), such that array becomes 15, 18,2,3,6,12 Solution So, to find the Nth largest element in normal sorted array is a[N]. But in this case it is rotated k, which we don’t know. [Read More]
search  ArraySearch  kodeknight  recursion  array  binary search  rotated array  kth-largest  min  sorted-array 

Find the rotation count in rotated sorted array

 Posted on August 24, 2013  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

**Question : **Find the minimum element in the rotated sorted array. So for example we have sorted array as - 2,3,6,12, 15, 18. Now suppose the array is rotated k times ( we don’t know k), such that array becomes 15, 18,2,3,6,12 Solution This can be solved in linear time and logarithmic time. If we notice the above array, we see the array has been rotated 2 times, which is also the index of smallest element in the array. [Read More]
ArraySearch  kodeknight  recursion  array  rotated array  count  min  sorted-array