Skip to main content

Posts

Showing posts from March, 2017

Binary Search Algorithm

Binary Search also known as Algorithmic or binary chop is a searching algorithm that searches for a element in a sorted data structure. Binary search is a searching algorithm that searches the required value by comparing the target value with the middle value of the array.

The following is the algorithm for binary search implementation

Step 0 : Sort the array using any sorting algorithm (I am using bubble sort in the below program)
Step 1 : Initialize first = 0 and last  = list.size() - 1
Step 2 :  while first < last and the element is not found calculate mid = (first + last) / 2
Step 3 : Compare target value with middle element
Step 4 : if the middle value is greater than the target value then target value lies on the left side of the middle value do goto step 1 with last = mid - 1
Step 5 : if the middle value is lesser than the target value then target value lies on the right side of the middle value do goto step 1 with first = mid + 1
Step 6 : if middle value is equal to the target va…

Finding Middle Node in Linked List

Linked List is dynamic data structure that is used to store information. Unlike arrays linked lists are not stored in contagious memory locations rather the are stored at any empty place in memory and the address of the next node is stored in the link field. Hence we don't have direct access to the Linked List elements as we do in arrays.

In order to find the middle node of the Linked List there are 2 methods

Method 1 : 
Traverse the Linked list count the number of nodes and then move a pointer to that node by using a counter. This method although useful requires us to traverse the List 2 times.

Method 2 : 
Use 2 pointers (say) fast and slow starting from the head node increment the fast pointer by 2 and increment the slow pointer by 1. In this way when the fast pointer reaches the end the slow pointer will point to the middle element.

To know more about Linked List and its implementation click Here.

The following is the implementation of the Method 2.  



C++ ProgramJava programPython Prog…

Mid-point Circle Generation Algorithm

Mid-Point circle generation algorithm aims to find out the points that lie on the circle (or approximately lie on the circle) in a pixel based display. This Algorithm is similar to Bresenhams Circle Generation Algorithm, According to wikipedia bresenhams algorithm is derived from mid-point circle generation algorithm.
In this algorithm we divide the circle into 8 parts and calculate the points only for one part and then apply the property of symmetry to get the points in the remaining 7 parts.

We divide the circle into the following parts.



At the beginning we start with the point x = 0, y = r ;
so we get the first point as (xc + x, yc + y) which lies on the circle. let us denote this point as (xp, yp).

now we have check if the neighbouring point (xp - 1, yp + 1) or (xp, yp + 1) lies on the circle, We do this by checking the value of the variable called parameter which checks if the point lies on the circle or not and accordingly we update the value of x and y to plot the next point.

Algorit…

Bresenhams Circle Generation Algorithm

Bresenhams circle generation algorithm aims to find out the points that lie on the circle (or approximately lie on the circle) in a pixel based display. In this algorithm we divide the circle into 8 parts and calculate the points only for one part and then apply the property of symmetry to get the points in the remaining 7 parts.

We divide the circle into the following parts.



At the beginning we start with the point x = 0, y = r ;
so we get the first point as (xc + x, yc + y) which lies on the circle. let us denote this point as (xp, yp).

now we have check if the neighbouring point (xp - 1, yp + 1) or (xp, yp + 1) lies on the circle, We do this by checking the value of the variable called parameter which checks if the point lies on the circle or not and accordingly we update the value of x and y to plot the next point.

Algorithm


Plot the initial point with x = 0, y = r and initialize parameter = 3 - 2*radiusWhile x < y keep repeating steps 3, 4 and 5If value of parameter is less than 0 t…