Nishesh Awale's Blog

Stack is one of the elementary data structure in which elements are added and deleted using Last-In-First-Out (LIFO) principle. To understand LIFO principle, let us consider a teacher is checking the examination paper. After checking each paper, he/she keeps the papers by his/her side such that the first paper checked, remained at the bottom and the last paper checked, remained at the top. So, the paper is inserted at the top of the pile of paper. While distributing the examination paper, the first paper to be removed, is the one which was on the top of the pile. This is known as LIFO principle. (a) Stack S has 4 elements and its top element is 9. (b) Stack S after STACK_PUSH(S, 17) and STACK_PUSH(S, 3). (c) Stack S after STACK_POP(S). [Source: Introduction to Algorithms] Here, we will see the implementation of stack using an array. Let, S[1…n] be the array. The stack has an attribute, S.top which gives index of the most recently added element. The stack is empty if S.top = ...

Binary search is used to locate an element in an array efficiently than the linear search. To use a binary search, the array must be sorted in non-decreasing order. If T[1…n] is the sorted array, then the binary search returns an index i at which the element(say x) is found. If the element is not in the array then, it returns a possible index where the element might be inserted. Here, we wish to find the index i such that 1 < i < n + 1 and T[i - 1] < x < T[i]. At first, let’s see how do we locate an element in an array using linear or sequential approach. LINEAR-SEARCH (T[1…n], x) for i = 1 to n if T[i] > x return i return n + 1 From the above algorithm, we can see clearly that the algorithm takes the time in θ(n) in the worst case where n is the number of elements. Now, let’s see how binary search algorithm will improve this running time. Basically, a binary search algorithm works like this. First, we compare the element x with the middle element of...

As we have seen previously that the running time of insertion sort is bounded by θ(n 2 ). Now we are interested in finding an algorithm that works better than insertion sort. Merge sort performs faster than insertion sort and it uses divide-and-conquer paradigm. So, what is divide-and-conquer paradigm? Divide: Divide the given problem into a number of subproblems that are smaller instances of the given problem. Conquer: Solve the problem recursively and when the size of problem becomes small enough then, solve it in the straight forward manner. Combine: Combine the solution of the subproblems to obtains the solution to the original problem. Divide-and-conquer paradigm applied to merge sort: Divide: Divide the given sequence of n-elements into two sequences with nearly half elements. Conquer: Sort the two sequences recursively using merge sort. Combine: Merge the two sorted sequence to produce the solution to the combined sequence. Now, let’s understand the m...

What is sorting? Suppose you are playing a multiplayer game with your friends on a computer. Each player is rewarded some points at the end of the game. As the game finishes, we need to display the score of each player on the screen with the lowest score at the bottom and the score gradually increases as we move toward the top. So, the process of arranging the numbers in this order is called sorting. How can we arrange numbers in such order? Well, there are different algorithms to do so but, here we discuss a basic algorithm called insertion sort. The concept of insertion sort can be easily understood with the following example. This example is taken from the CLRS book Introduction to Algorithms . Suppose we have to sort a hand of playing cards. Initially, the left hand is empty and the cards are facing down on the table. We then, remove a card from the table at a time and place it in the right position on the hand. To do so, we compare the card (say X) which we picked with the r...