Dijkstra's Shortest Path Algorithm
Posted on August 4, 2013
(Last modified on August 7, 2020)
| 6 minutes
| Kinshuk Chandra
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]Adjacency list represention of graph in Java
Posted on August 4, 2013
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Here is the program for adjacency list representation of graphs using java. If you are new to Graphs please read about graphs here before reading the rest of this post.
Code:
package com.vaani.algo.graph.impl; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; public class GraphUsingAdjList { class Node { int node; List<Integer> adjList; boolean visited; } void insertVertices() throws IOException { BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); System.out.println("Enter number of nodes in a graph: "); int n=(Integer.
[Read More]Graph Search Introduction
Posted on August 3, 2013
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
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]How do I check if a number is a palindrome?
Posted on August 3, 2013
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Testing the coment
Kinshuk Chandra - Aug 6, 2013
Testing the coment
How do I check if a number is a palindrome?
Posted on August 3, 2013
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Note:
First, the problem statement did not specify if negative integers qualify as palindromes. Does negative integer such as -1 qualify as a palindrome? Finding out the full requirements of a problem before coding is what every programmer must do. For the purpose of discussion here, we define negative integers as non-palindromes.
Approaches to solve the problem
Approach 1:
The most intuitive approach is to first represent the integer as a string, since it is more convenient to manipulate.
[Read More]Operation time complexity for a LINKED LIST
Posted on July 30, 2013
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
The time complexity of handling the operations in a data structure like a LINKED LIST are as follows:
i. Most of the operations are O(n) [i.e. omega times n]
ii. Remove/Insert operations that handles element between elements require O(1) [i.e. omega times one] this is due to references/pointers on both the ends of the list, hence the elements don’t require to be shifted. However, due to the references/pointers this data structure requires additional memory!
[Read More]Operation time complexity for an ARRAY
Posted on July 30, 2013
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
The time complexity of handling the operations in a data structure like an ARRAY are as follows:
i. Almost all the operations are O(1) [i.e. omega times one]
ii. Remove/Insert operations that handles element between elements require O(n) [i.e. omega times n] because the elements need to be shifted.
Note! Hence, an array as a data structure is used where remove/insert operations are not required.
Time complexity - Omega of algorithms
Posted on July 30, 2013
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
a) if statement - O(n) [Omega times n]
b) for loop - O(n) [Omega times n]
c) for loop with a for loop - O(n*n) [Omega times n squared]
d) for loop within a if loop, this if loop is within a for loop - O(n + n*n) [n plus n squared omega]
e) while loop - O(n) [Omega times n]
f) MergeSort - O(nlogn) [Omega n time logarithmic n]
[Read More]Time complexity of algorithms - In particular Big Omega of algorithms
Posted on July 30, 2013
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Big Omega or so called asymptotic upper bound of algorithms such as Sequential statements, If statements and Looping construct
(i) Sequential statements:
Big Omega of this algorithm equals to maximum time complexities of all individual statements (i.e. sum of maximum time complexities of the individual statements)
Therefore, O[g(n)] = O{f1(n)+f2(n)+ … +fk(n)}
Conclusion: Overall complexity of this algorithm equates to O[g(n)]
(ii) If statements:
Big Omega of this algorithm equals to maximum time complexities of either one of the alternative statements i.
[Read More]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]