0

Print singly linked list in reverse order

Problem:

Printing singly linked list is a little tricky problem because singly linked list only stores address to of the next node, no previous node address is stored in any node.

Logic:

This problem can be solved easily using recursion. Recursively call PrintReverse function till root is not null and start print.

For last node his next is null, so for that null function will return and executing line below recursive call will start execution which will start printing node values. As print line execution starts from last node, linked list will be printed in reverse order.

Implementation:

0

Heap Sort

What is a heap?

Heap data structure is an array that can be viewed as a complete binary tree. Which means each node of a tree corresponds to a element in array. Remember complete binary tree?  Complete binary tree is a type of binary tree in which all levels are completely filled except last level which is filled from left to right.

Consider array [4,2,8,3,6,5,1] So first element of array forms a root of a tree.

Heap

If we consider array index staring from 1 instead of 0. We can consider how we decide left , right children and parent node of a tree. i is index of array.

Parent : i / 2

Left child:  2 * i

Right child: (2 * i) + 1

If we consider element at index 1 is parent its children will be left child (2*1=2) element at index 2 (2) and right child will be ((2*1)+1 = 3) (8).

If you want to find parent of 6 then you don’t need o picture a tree, using formula one can know that. 6’s index is 5. 5/2=2 so element at index 2 , which 2 is going to be 6’s parent.

If you consider his example, you can see a binary tree can have parent nodes till n/2, if ‘n’ is total number of elements. As each parent will have at the max 2 children, (n/2) + 1 to n  will be leaf nodes.

Heap data structure is of 2 types, Max heap and Min heap.

Max heap:  Value of parent node is always greater than value of its children.

Min heap:  Value of parent node is always minimum than value of its children.

So how heap sort uses min heap or max heap property of heap data structure to sort elements?

Logic:

1. Build a max heap (or min heap depending on the order in which need o sort elements).

2. Place root key in back in array and replace root with leftmost leaf node. Form max heap again and repeat this step again.

Example:

Consider input array as: [4,2,,8,3,6,5]

Heap Sort

Implementations:

Explanation:

1. In each call we are going to do heap by calling heapify function and then  swap first element of array(which is root of a tree)  with last element of array ( which is leaf node of tree).  Now after swapping new root may violate a max heap property, but children are max heaps.

2.  In Heapsort call , for loop is from [length-1 to 1] because we will decrease heap size by 1 in each call.

3. In Heapify function call, for loop is from [length/2 to 1] because we know that in array all elements from [length/2+1 to length-1] going to be leaf nodes.

Analysis:

Each call to Heapify function costs O(lg n) time, and HeapSort makes O(n) such calls. So running time for HeapSort is O(n lg n).

Heap sort is  in place and stable sorting algorithm.

0

Merge Sort

If you are given 4 red sticks of different heights placed from lower to higher height order and 4 green sticks of different heights placed from lower to higher height order. Task is to arrange red and green sticks together from lower to higher height..

A basic way to do this is to pick smallest by comparing smaller sticks of red and green  and place it. Next pick 2nd  highest stick. Continue this till all sticks are placed in correct order. In Merge sort this basic technique of merging to sorted array is used.

MergeExample

Logic:

Merge sort uses a concept of ‘divide and conquer‘ to sort elements.

a.  Divide given elements in half, continue dividing elements unless there is only one element present to sort. As one element is always a sorted element, return and start next step.

b. Merge two elements together in a sorted order. continue merging two sorted sub arrays till all input elements are in sorted order.

Example:

Consider input elements as 4,2,8,1,6,3

MergeSort

Dividing action is performed by calling MergeSort function recursively, in each call mid of  array is calculated and two subarrays are formed like input[start to mid] and input[mid+1 to end] and sorting and merging two subarrays is performed by calling Merge function recursively.

 

Implementation:

 

Analysis:

Calculating mid of array takes  constant time regardless of size of the array . So time complexity of this operation is O(1).

When we combine two sorted array , each element is checked so time complexity for this operation is O(n)

In each step array is divided in half and sort two subarrays of size n/2. So the total time complexity of  sorting n elements can be expressed as following :

T(n) = T(n/2) + T(n/2) + O(n)    :: T(n)=2T(n/2) + O(n)

By using Master theorem, Time complexity is O(nlog n)

Merge sort uses an extra space to hold two halves so his sort is not a in place sort and space complexity is O(n).

0

How to Edit a control template XAML

Follow the following steps to edit control template or access it.

1. Open your .xaml file

2. Right click on your control

3. Click on Edit Template, then click on Edit Copy.

4. Then you can decide whether you want apply this template to only this control or apply all existing. Also Where you wanna define it

5. After this you will see the xaml code for that control, you can edit it the way you want !!

In Xaml go to your control, I have taken “Button” as my control

CreateButton

In Designer Right Click on the Button Control -> Edit Template -> Edit Copy.

 

EditCopy

Do you want to apply to all Buttons ? or create a new Style with custom Name(key) use it only one certain buttons ! Also Where do you want to define this style ?

SelectApplication

 

After you hit Okay you will see the Button Style Template !! Enjoy !!

0

Introduction to Recursion

Recursion ?

Recursion means recursion. 🙂

Google explains Recursion in there way, just try searching recursion and see what happens :

recursion

So you got the idea now that recursion has something to do with Repetition. Let’s first go throw the formal definition of recursion from Wikipedia :

Recursion is the process of repeating items in a self-similar way.

Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem (as opposed to iteration).[1] The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science.[2] – Wikipedia

In programming Language recursive method is the one which calls it self. For example consider the following example :

The above code has a method called Recursion(int x)  that takes integer x as an argument. This method prints the string “Recursing” x times. I will show you what exactly happens in the stack when you write the above code.

Whenever you call a function, it is added to the call stack. The Function last added to call stack is executed first.

For above code, we will start from main :

 

 

0

Searching – Linear search

Searching is a very important problem in field of computer science.

Searching can be divided into three main categories :

1) Linear search
2) Binary search
3) Hashing.

This post will explain Linear search.
Linear search is simply iterating through all the elements of array , till you find the item in question.
Worst case complexity of this algorithm is O(N) while best case is O(1).

For example : Given a List of N elements find element x. If present, return its position.

Lets write a simple method to implement Linear search. See following method LinearSearch() this method takes two parameters, first is an array of integers and second is the element to search in that array.

So above method returns -1 if element is not present in the array or returns its position in array, if  present. Linear search is very simple to understand and implement.