Posts

Queue

Image
Previously, we have seen how a stack works. In this blog, I want to give you some insights on another elementary data structure, queue. Queue works on First-In-First-Out (FIFO) principle. Queue can be modeled in real life by a line of customers waiting to pay the bill. The new customers are added at the end of the queue and the customer at the front of the queue comes out after paying the bill. Similar to the push and pop operation of stack, queue has enqueue and dequeue operation. Enqueue adds the element to the end of the queue while dequeue removes the first element from the queue. (a) Queue Q has 5 elements at location Q[7...11]. (b) Queue Q after ENQUEUE(Q, 17), ENQUEUE(Q, 3), and ENQUEUE(Q, 5). (c) Queue Q after DEQUEUE(Q). [Source: Introduction to Algorithms] Here, we implement a queue using an array Q [1…n]. Queue has its attribute, Q.head which points to the head of the queue. Also, Q.tail points to the next location at which the new element will be inserted. When Q...
Post a Comment
Read more

Stack

Image
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 = ...
Post a Comment
Read more

Binary Search

Image
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...
1 comment
Read more

Merge Sort

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...
Post a Comment
Read more

Insertion Sort

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...
Post a Comment
Read more

Differences between hardwired and micro-programmed control unit

S.N. Hardwired Control Unit Micro-programmed Control Unit 1. It is implemented through the use of sequential logic circuit. Its input logic signals are transformed into a set of output logic signals which are control signals. It is implemented through the use of micro-programs. Micro-programs (control information) are organized as a sequence of micro-instructions stored in a special control memory. 2. This design uses a fixed architecture so, it require changes in wiring if the instruction set is modified. It is easy to reconfigure and modify instruction set. 3. It is difficult to build a circuit that satisfies all the operations. It is simple in structure. 4. It has faster mode of operation. It is comparatively slower. 5. It is comparatively expensive. It is cheaper. 6. It is preferred for less number of instruction sets. I...
Post a Comment
Read more

System Bus

Image
Have you ever wondered how the microprocessor communicates with the devices connected to it? Well, there are a group of wires (communication path) between microprocessor and its peripherals (and memory) to carry bits which are known as system bus. The system bus performs the following steps to communicate with the peripheral: i.         Identify the peripheral or the memory location (with its address). ii.       Transfer data and instructions in the form of bits. iii.     Provide timing and synchronization signals. According to the above functions, system bus can be classified into three types which are described below: Address Bus: It is a set of wires that is used to transmit address from the microprocessor to its peripheral devices (or memory. It is unidirectional. Each peripheral or memory is identified by its address. This is similar to the postal address of the house. For example...
Post a Comment
Read more