Category Archives: Algorithm

AVL Tree

B+ Tree

Floyd Warshall Algorithm

Bellman Ford

It works on negative cycle.

Implemented Code:

Time Complexity:

O([E].[V])

Reference:
http://cyberlingo.blogspot.com/2015/07/bellman-ford-algorithm.html

Dijkstra

output:

Complexity:
O(E+V^2)

We are using here adjacency matrix list

Topological Sort

code:

Output:

Time Complexity: O(V+E)
Space Complexity: O(V)
V for vertex E for edge

code courtesy:

Topological Sorting

I understood the theory but need to understand the code well later

Bucket Sort

Pseudocode:

Implemented Code:

output:

 

Tuts:

Reference:
CLRS: http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/bucketSort.htm

Bucket Sort

Harumanchi Book implementation:

output:

 

Time and Space complexity: O(n)

Radix Sort

best video:

pseudocode:

implementation: (I need to clear the radix sort part later..took help to implement)

Reference:

Radix Sort – Explanation, Pseudocode and Implementation

Time complexity: O(d*n)==O(n)
Where d is the digit of the number

Counting Sort

Algo:

Implemented Code:

 

Reference:
http://scanftree.com/Data_Structure/Counting-sort

Counting Sort in C

CLRS:
http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/countingSort.htm

Tuts:

Complexity:
Time: O(k)+O(n)+O(k)+O(n)=O(n) if K=O(n)
Space: O(n)

Binary Search Tree: Successor in Inorder Traversal

code:

 

Delete a node in Binary Search Tree

code:

Traversal in Binary Search Tree

Height of a binary tree:

 

Level Order BFS in Binary Search Tree:

output:


DFS in Preorder, Inorder, Postorder:

output:

 

 

Binary Search Tree

youtube :

code:

 

Heap Sort

Steps:
If we want to sort in ascending then we create a min heap
If we want to create in descending then we create in max heap

Once the heap is created we delete the root node from heap and put the last node in the root position and repeat the steps till we have covered all the elements.
For ascending order:
1. Build Heap
2. Transform the heap into min heap
3. Delete the root node

pseudocode:

source:
http://www.algorithmist.com/index.php/Heap_sort

Implemented code:

output:

Took help from these two links:
http://www.codingeek.com/algorithms/heap-sort-algorithm-explanation-and-implementation/
http://www.geeksforgeeks.org/heap-sort/

Complexity Analysis:
Time Complexity for MaxHeapify: O(logn)
Complexity for BuildHeap: O(n)
Complexity of heapSort:
Worst, Avergae, Base case: O(n*logn)
It is inplace algorithm.
Space Complexity: O(1)

Big Oh, Theta and Omega Notation confusion clearing

https://stackoverflow.com/questions/471199/what-is-the-difference-between-%CE%98n-and-on