Facebook

Computer Science

Decision Making Statements

Decision Making Statements are the statements that imposes one or more conditions on the expression and if the conditions evaluates to be true then specific actions are followed,if not true then some other actions are followed.They are called as decision making as it leads to a particular conclusion/decision.In C,true values are treated as non-zero i.e.1… read more »

Functions

A function is a group of statements that performs some specific task.They can be used in other programs depending on their accessibility and are ended by brackets.In order to define a function inside  a program we need to specify three things: Function Declaration Function Definition Function Calling Some functions are pre-defined like main(),printf(),scanf().We just need… read more »

Merge Sort

Merge sort is the divide and conquer method to arrange elements in the order.The steps followed in merge sort are : Divide the sequence of n elements into two sub-sequences of n/2 elements each. Sort the sub-sequences using merge sort.If the size of sequence is 1,nothing more can be done. Merge the sub-sequences to form… read more »

Bubblesort

Bubblesort is a sorting technique which arrange elements in the increasing order by moving across the array and swapping the adjacent elements that are out of order.The complexity of bubble sort is O(n2). The steps followed are : Move from first to the last element of array. Swap the element if it is greater than… read more »

Quicksort

Sorting is a technique to arrange the sequence of elements either in ascending or descending order. Quicksort is an efficient way to sort elements of array.The average running time of quicksort is O(nlogn).The steps followed in quicksort are : Choose the pivot element(Say we choose the pivot element in the beginning of array).  Scan from… read more »

Operations on Binomial Heap – Decrease key

Decrease key refers to reducing the key value of any node.If we want to decrease a key in Binomial heap,we will replace the key with reduced value and will repeatedly exchange the reduced key with the parent in order to restore min-heap property.The running time to perform this operation is O(log n). Example Say we… read more »

Operations on Binomial Heap – Extract-min

In Extract-Min operation node with minimum key is deleted from the binomial heap h.The running time to extract minimum value is  O(log n).The steps followed  are : Find the root (say x) with minimum key. Delete the root. Break the binomial heap into h and h’. Perform the union operation to h and h’. Given the… read more »

Operations On Binomial Heap – Union

The union of two heaps is the merging root lists by root degree.But if we simply merge two heaps then a problem can arise.There may be a chance that we get two or more trees of same root degree.This violates the property of binomial heap.To deal with this problem we have four cases and solution… read more »

Binomial Heaps

Binomial Heaps are similar to binary heaps with additional feature of implementing binomial series as sequence of trees.The heap(Fig 1) is represented using left child right sibling pointers.It has three links per node (parent,left,right) and the roots of tree are connected using single linked list.The degrees of tree decrease from left to right. Properties of… read more »

Binomial Trees

Binomial Trees are one of  the type of trees that are defined  recursively.A Binomial tree of order 0 is a single node and a binomial tree of order n has a root node whose children are roots of binomial trees of order n-1,n-2,n-3,n-4,……3,2,1,0. Properties of Binomial Tree There are 2n nodes in a binomial tree of order n where… read more »

Sidebar