90629cf6-230e-4134-84bd-08229d87c2a6-1571835704584-dsa.pdf

DATA STRUCTURES AND ALGORITHMS For COMPUTER SCIENCE  DATA STRUCTURES &. ALGORITHMS SYLLABUS Programming and Data Structures: Programming in C. Recursion. Arrays, stacks, queues, linked lists, trees, binary...

DATA STRUCTURES AND ALGORITHMS For COMPUTER SCIENCE  DATA STRUCTURES &. ALGORITHMS SYLLABUS Programming and Data Structures: Programming in C. Recursion. Arrays, stacks, queues, linked lists, trees, binary search trees, binary heaps, graphs. Algorithms: Searching, sorting, hashing. Asymptotic worst case time and space complexity. Algorithm design techniques: greedy, dynamic spanning trees, shortest paths. ANALYSIS OF GATE PAPERS Data Structures Algorithms 1 Mark 2 Mark 1 Mark 2 Mark Exam Year Ques. Ques. Total Exam Year Ques. Ques. Total 2003 5 7 19 2003 3 5 13 2004 7 10 27 2004 1 7 15 2005 5 6 17 2005 2 7 16 2006 1 7 15 2006 7 5 17 2007 2 7 16 2007 2 8 18 2008 3 7 17 2008 - 11 22 2009 1 4 9 2009 3 5 13 2010 1 5 11 2010 1 3 7 2011 1 3 7 2011 1 3 7 2012 1 4 9 2012 3 3 9 2013 - 3 6 2013 4 3 10 2014 Set-1 3 3 9 2014 Set-1 2 2 6 2014 Set-2 3 3 9 2014 Set-2 2 2 6 2014 Set-3 3 3 9 2014 Set-3 1 3 5 2015 Set-1 3 3 6 2015 Set-1 3 3 9 2015 Set-2 3 2 4 2015 Set-2 3 3 9 2015 Set-3 4 6 16 2015 Set-3 2 3 8 2016 Set-1 3 5 13 2016 Set-1 2 3 8 2016 Set-2 3 6 15 2016 Set-2 2 2 6 2017 Set-1 4 3 10 2017 Set-1 2 1 4 2017 Set-2 2 4 10 2017 Set-2 1 3 7 2018 4 3 10 2018 1 3 7 © Copyright Reserved by Gateflix.in No part of this material should be copied or reproduced without permission  CONTENTS Topics Page No 1. INTRODUCTION TO DATA STRUCTURES 1.1 Introduction 01 1.2 Linked Lists 01 2. STACK AND QUEUE 2.1 Stack 06 2.2 Queues 09 2.3 Deque 12 2.4 Abstract Data Types 12 2.5 Performance Analysis 12 2.6 Asymptotic Notation (o, Ω, ϴ) 13 3. SORTING & SEARCHING 3.1 Sorting 15 3.2 Sorting, Algorithms 15 3.3 Searching 25 4. TREE 4.1 Binary Tree 29 4.2 Header Nodes: Threads 36 4.3 Binary Search Trees 38 5. HEAP & HEIGHT BALANCED TREE 5.1 Heap 42 5.2 Tree Searching 44 5.3 Optimum Search Trees 46 5.4 General Search Trees 49 5.5 Multiday Search Trees 49 5.6 B– Tree and B+ Tree 50 5.7 Digital Search Tree 52 6. INTRODUCTION TO GRAPH THEORY 6.1 Graph Theory Terminology 55 6.2 Direct Graph 57 © Copyright Reserved by Gateflix.in No part of this material should be copied or reproduced without permission  6.3 In Degrees and Out Degrees Of Vertices of a Diagram 58 6.4 Null Graph 58 6.5 Finite Graphs 58 6.6 Trivial Graphs 58 6.7 Sub Graphs 58 6.8 Sequential Representation of Graphs, Adjacency Matrix, Path Matrix 58 6.9 Shortest Path Algorithm 60 6.10 Linked Representation of a Graph 60 6.11 Graph Traversal 62 6.12 Spanning Forests 62 6.13 Undirected Graphs and Their Traversals 63 6.14 Minimum Spanning Trees 67 7. DESIGN TECHNIQUES 7.1 A Greedy Algorithm 69 7.2 Divide and Conquer Algorithm 70 7.3 Dynamic Programming 71 7.4 Backtracking 72 8. GATE QUESTIONS (DATA STRUCTURES) 75 9. GATE QUESTIONS (ALGORITHMS) 136 10. ASSIGNMENT QUESTIONS (DATA STRUCTURES) 184 11. ASSIGNMENT QUESTIONS (ALGORITHMS) 200 © Copyright Reserved by Gateflix.in No part of this material should be copied or reproduced without permission  1 INTRODUCTION TO DATA STRUCTURES 1.1 INTRODUCTION i) A fixed amount of storage remains allocated to the stack or queue even A computer is a machine that processes when the structure is actually using information and data. The study of data a smaller amount or possibly no structures includes how this information storage at all. and data is related and how to use this data efficiently for various applications. ii) Only fixed amount of storage may be allocated, making overflow a possibility.  In a sequential representation, the items of a stack or a queue are implicitly ordered by the sequential order of storage. If q[x] represents an element of a queue, the next element will be q [(x+1) % MAXQUEUE] i.e. if x equals MAXQUEUE -1 then next element is q.  Suppose that the items of a stack or a queue are explicitly ordered i. e. each Fig 1: Value and Operator Definition item contain the address of the next item within itself. Such an explicit  A logical property of a data type is ordering gives rise to a data structure specified by abstract data type, or ADT. known as a Linear linked list as shown  A data type definition consist of: in the figure 2. (i) Value definition i.e. values and (ii)Operator definition i.e. set of operations on these values.  These values and the operations on them form a mathematical construct that can be implemented using Fig 2: Linked List hardware or software data structures. Note: ADT is not concerned with  Each item in the list is called a node and implementation details. it contains two fields.  Any two values in an ADT are equal if i) Information field: It holds the actual and only if the values of their element on the list. components are equal. ii) The next address field: It contains the address of the next node in the 1.2 LINKED LISTS list. Such an address, which is used to access a particular node, is known  There are certain drawbacks of using as a pointer. sequential storage to represent stacks  The entire linked list is accessed from and queue. an external pointer (list) that points to (contains the address of) the first node in the list. © Copyright Reserved by Gateflix.in No part of this material should be copied or reproduced without permission   The next address field of the last node in the linked list contains a special value called as null. This is not a valid address and used to signal the end of a list. Fig 3: Adding an element to front of  The linked list with no nodes is called linked list the empty list or the null list. The value of the external pointer, list, to such a For example: linked list is the null. The list can be Suppose that we are given a list of integers initialized to form the empty list by the as illustrated in fig 3(a) and we have to add operation list = null. the integer 6 to the front of that linked list. 1.2.1 INSERTING AND REMOVING NODES  Assume the existence of mechanism for FROM A LIST obtaining empty nodes as P = getNode ( ); 1.2.1.1 Insertion The operation obtains an empty node and sets the contents of a variable A list is a dynamic data structure, the named P to the address of that node. number of nodes on a list may vary as The value of P is then a pointer to this elements are inserted and removed. The newly allocated node. dynamic nature of a list may be contrasted  fig 3(b), shows the list and the new with the static nature of an array, whose node after performing the get node size remains constant. operation. The next step is to insert the integer 6 into the info portion of the newly allocated node. This is done by info (P) = 6; (The result is shown in fig. 3(c))  After setting the info portion of node (P), it is necessary to set the next portion of that node. Since node (P) is to be inserted at the front of the list, the node that follows should be the first node of the current list. Since the variable list contains the address of that first node, node (P) can be added to the list by performing the operation next (P) = list; [This operation places the value of list (which is the address of first node fn the list) into the next field of node(P)]  At this point, P points to the list with the additional item included. However, since list is the external pointer to the desired list, its value must be modified to the address of the new first node of the list. This can be done by performing the operation – list = P; © Copyright Reserved by Gateflix.in No part of this material should be copied or reproduced without permission  Which changes the value of list to the Note: The process is exactly opposite to the value of P. Fig 3(e) illustrates the result process of adding a node of this operation. During the process of removing the first  Generalized Algorithm node from the list, the variable p is used as 1. P=getNode ( ); //Allocate an auxiliary variable. The starting and memory for new node ending configuration of the list make no 2. Info (P) =x; reference to P. But once the value of p is 3. Next (P) =list; changed there is no way to access the node 4. List=P; at all, since neither an external pointer nor a next field contains its address. Therefore 1.2.1.2 Deletion the node is currently useless and cannot be reused. The get node creates a new node, The following figure 4 shows the process of whereas free node destroys a node. removing the first node of a nonempty list and storing the value of its info into a Linked List as a Data Structure variable x. The initial step and final step is Linked Lists are not only used for as shown in fig 4(a) and 4(f) respectively- implementing stacks and queues but also other data structures. An item is accessed in a linked list by traversing the list from its beginning. A list implementation requires n operation to access the nth item in a group but an array requires only single operation. Inserting or deleting an element in the middle of a group of other elements list is superior in an array. For example: Fig 5: Insertion operation We want to insert an element x between the 3rd and 4th elements in an array of size 10 that currently contains seven items (X through X ). Items 6 to 3 first are moved one slot and the new element is inserted in the newly Fig 4: Removing a node from the front of available position 3 as shown in the fig 5. the linked list  In this case insertion of one item involves moving four items in addition © Copyright Reserved by Gateflix.in No part of this material should be copied or reproduced without permission  to the insertion itself. If the array 1.2.2 OTHER LIST STRUCTURES contained 500 or 1000 elements, a correspondingly larger number of 1.2.2.1 Circular Lists elements would have to be moved. Similarly to delete an element from an  Let p be a pointer to a node in a linear array without any gap, all the elements list, but we cannot reach any of the beyond the element deleted must be nodes that precede node (p). If a list is moved one position. traversed, the external pointer to the  Suppose the items are stored as a list, if list must be preserved to be able to p points to an element of the list, reference the list again. inserting a new element involve Suppose that a small change is made to allocating a node, inserting the the structure of a linear list, so that the information and adjusting two pointers. next field in the last node contains a The amount of work required is pointer back to the first node rather independent of the size of the list as than the null pointer. Such a list is shown in fig 6. called a circular list  Circular list is as shown in fig. 7(a), from any pointy in such a list it is possible to reach any other point in the list. If we begin at a given node and traverse the entire list, we end up at the starting point. Note: Circular list does not have a natural “first” or “last” node. We must therefore, establish a first and last node by Fig 6: inserting a node convention.  An item can be inserted only after a given node, because there is no way to proceed from a given node to its predecessor in a linear list without traversing the list from its beginning i.e. one can only go forward for accessing the node of the list, not backward.  For insertion of an item before desire node, the next field of its predecessor must be changed to point to a newly allocated node.  To delete a node from a linear list it is insufficient for only one given pointer to that node. Since the next field of the Fig 7: Circular linked list node’s predecessor must be changed to One convention: Let the external pointer point to the node’s successor and there to the circular list point to the last node, is no directed way of reaching the and to allow the following node to be the predecessor of a given node. first node as shown in fig. 7 (b). If p is an external pointer to a circular list, this convention allows access to the last node , this convention allows access to the last node of the list by referencing node(p) and © Copyright Reserved by Gateflix.in No part of this material should be copied or reproduced without permission  to the first node of the list by referencing  Dynamic implementation and array node (next(p)). implementation of each node is as A circular list can be used to represent a shown in fig. 8. stack or queue. 1.2.2.2 Doubly Linked Lists Although a circularly linked list has advantages over a linear list but still it has some drawbacks listed as follows:  One cannot traverse such a list backward, nor can a node be deleted from a circularly linked list, given only a pointer to that node. In case where these facilities are required, the suitable data structure is a Fig 8: Array and dynamic implementation doubly linked list.  In Doubly Linked Lists each node Note: In the array implementation the contains two pointers: one to its available list for such a set of nodes need predecessor and another to its not be doubly linked, since it is not successor. traversed bidirectional. The available list must be linked together by using either a  Doubly linked list may be either left or a right pointer. linear or circular and may or may not contain a header node.  Nodes on a doubly linked list consists of three fields (i) An info field that contains the value stored in the node. (ii) Left and right field contains pointers to the nodes on either side © Copyright Reserved by Gateflix.in No part of this material should be copied or reproduced without permission  2 STACK AND QUEUE 2.1 STACK than from a side looking in. Thus there is no perceptible difference between A stack is an ordered collection of items frame (E) and (D). One can compare the into which new items may be inserted or stacks at the two frames by removing deleted only at one end, called the top of all the elements on both stacks and the stack. compare them individually. 2.1.1 OPERATIONS ON STACK  When an item is added to a stack, it is pushed onto the stack.  When an item is removed, it is popped from the stack.  Given a stack s and an item i, performing the operation push (s, i) adds item i to the top of stack s. Fig 1: Stack containing elements  The operation i = pop(s); removes the  A stack is different from an array as it element at the top of s and assigns its has the provision for the insertion and value to i. deletions of items, thus a stack is a  As push operation adds elements on to dynamic, constantly changing object. a stack, so a stack is sometimes called a  The last element inserted into a stack is pushdown list. the first element deleted. Thus stack is  There is no upper limit on the number called a last-in, First-out (or-LIFO) list. of items that may be kept in a stack; though pop operation cannot be applied to the empty stack as such a stack has no elements to pop.  The operation empty(s) determines whether stacks are empty or not. If the stack is empty, empty or not. If the stack is empty, empty(s) returns the value TRUE, or else it will return the value FALSE. Fig 2: Motion picture of stack  The operation stack top(s) returns the top element of stack s. The stack top(s)  One cannot distinguish between frame operations can be decomposed into a (A) and frame (E) by looking at the pop and a push. This is also called as stack’s state at the two instances. No peek operation. record is kept on the stack of the fact i = stack top(s); is equivalent to that items had been pushed and popped i = pop(s); in the meantime. push (s, i);  The true picture of a stack is given by a view from the top looking down, rather © Copyright Reserved by Gateflix.in No part of this material should be copied or reproduced without permission  The result of an illegal attempt to pop 2.1.3 Evaluation of a Postfix Expression or access an item from an empty stack Let P be an arithmetic expression written is called underflow in postfix notation. The following algorithm Operation Function evaluates P using a STACK to hold Push(s, i) Adds item i on the top of operands. stack s. Pop(s) Removes the top element of Algorithm: the stacks 1. Add a right parenthesis”)” at the end of P. Empty(s) Determines whether or not 2. Scan P from left to right and repeat a stack steps 3 and 4 for each elements of P Stack Return the top element of until the “)” is encountered. top(s) stacks without popping it 3. If an operand is encountered, push it on stack top is not defined for an empty stack. STACK. 4. If an operator is encountered, then 2.1.2 INFIX, POSTFIX AND PREFIX (a) Remove the two top elements of STAC, where X is the top element  If the operator is situated in between and Y is the next to top element. the operands, then the representation is (b) Evaluate Y operator X. called infix. (c) Place the result of A+ B  infix (d) back on STACK.  If the operator is preceding the [End of loop] operands, then the representation is 5. Set VALUE equal to the element on called prefix. STACK. +AB  prefix 6. Exit.  If the operator is following the operands, then the representation is Example of Above Concept: called postfix. Consider the following arithmetic AB+  postfix expression P written in postfix notation.  Examples of Polish / Prefix notation P: 4,5,2, +, *, 16, 4, /, - [ , is for separation 1. (A + B) * C = (+ AB) * C = * + ABC it’s not an operator] 2. A + (B * C) = A + (*BC) = +A * BC Below is the content of STACK as each 3. (A+B)/(C-D) = (+AB) / (-CD) = /+AB element of P is scanned. – CD  Examples of Reverse polish / postfix Symbol Scanned STACK Notation 4 4 1. A $ B * C- D + E / F/ (G + H) = AB $ C 5 4,5 * D – EF / GH +/+ 2 4,5,2 2. ((A + B) *C-(D-E)) $ (F + G) = AB +C + 4,7 * DE - - FG + $ * 28 3. A –B /(C * D $ E) = ABCDE $ * / - 16 28,16  The computer evaluates an arithmetic 4 28,16,4 expression written in infix notation in / 28,4 two steps, i.e. first it converts the - 24 expression to postfix notation and then ) it evaluates the postfix expression. The final number in STACK is 24, which is assigned to VALUE when “)” is scanned and thus is the final value of P. © Copyright Reserved by Gateflix.in No part of this material should be copied or reproduced without permission  2.1.4 Infix to Postfix Conversion Example - Consider the following arithmetic infix Let Q be an arithmetic expression written expression Q: in infix notation, besides operands and Q: A + (B * C-(D/E  F)*G)*H operators, Q also contain left and right Following is the process of conversion of parentheses. infix expressions into its equivalent The following algorithm is used to expression P. transform the infix expression Q to its equivalent postfix expression P. It uses a Symbol STACK Expression P stack to temporarily hold operators and left Scanned parentheses. The postfix expression P will A ( A + (+ A be constructed from left to right using the ( (+( A operands from Q and the operators which B (+( AB are removed from STACK. Push a left * (+(* AB parenthesis onto STACK and add a right C (+(* ABC parenthesis at the end of Q. The algorithm - (+(- ABC* is completed when STACK is empty. ( (*(- ABC* Algorithm: D (+(-( ABC*D / (+(-(/ ABC*D E (+(-(/ ABC*DE 1. Push “(“onto STACK, and add “)” to the ↑ (+(-(/↑ ABC*DE end of Q. F (+(-(/↑ ABC*DEF 2. Scan Q from left to right and repeat ) (+(- ABC*DEF↑/ steps 3 to 6 for each elements of Q until * (+(-* ABC*DEF↑/ the STACK is empty. G (+(-* ABC*DEF↑/G ) (+ ABC*DEF↑/G*- 3. If an operand is encountered, add it to * (+* ABC*DEF↑/G*- P. H (+* ABC*DEF↑/G*-H 4. If a left parenthesis is encountered push ) ABC*DEF↑/G*-H*+ it onto STACK 5. If an operator  is encountered, then: After last step, the STACK is empty and (a) Repeatedly pop from STACK and postfix equivalent of Q is add to P, each operator (on the top P: ABC * DEF  /G* -H * + of STACK) which has the same precedence or higher precedence 2.1.5 LINKED IMPLEMENTATION OF than . STACKS (b) Add  to STACK [End of if structure] The operation of adding an element to the 6. If a right parenthesis is encountered, front of a linked list is similar to that of then: pushing an element onto a stack. A new (a) Repeatedly pop form STACK and item is addressed as the only immediately add to P each operator (on the top of accessible item in a collection –in both STACK) until a left parenthesis is cases. encountered. (b) Remove the left parenthesis. Note: A stack can be accessed only through its top element and a list can be [Do not add the left parenthesis to P] accessed only from the pointer to its first [End of If structure] element and the operation of removing the [End of step 2 loop] first element from a linked list is similar to 7. Exit popping a stack. © Copyright Reserved by Gateflix.in No part of this material should be copied or reproduced without permission  A stack may be represented by a 2.2 QUEUE Linear Linked List. The first node of the list represents the top of the stack. A queue is an ordered collection of items from which items may be deleted at one If an external pointer s points to end called the front of the queue and may such a linked list, the operation push(s, x) be inserted at the other end called the rear is implemented as: or the queue. 1. P=getNode ( ); The first element inserted into a queue into 2. Info (p) =x; a queue is the first element to be removed. 3. next (p)=s; Thus queue is called a FIFO (first – In – 4. s=p; First – Out) list. Consider the following figure 2.2.1 Operations on Queue Operation Function Insert Inserts item x at the rear of the queue q x=remove(q) Deletes the front elements from the queue q and sets x to its contents Empty Returns false on true depending on whether or not the queue contains any elements. Fig 3: Stack and queue as linked list Fig. 3(a) shows a stack implemented as a linked list fig. 3(b) shows the same stack after another element has been pushed onto it. Advantages:  All stacks being used by a program can share the same available list and when a stack needs a node, it can obtain it from the single available list. Fig. 4: Insertion of element in Queue  When a stack no longer needs a node, it returns the node to that same available Example: list.  As there is no limit to the number of  As long as the total amount of space elements a queue may contain, so an needed by all the stacks at any one time insert operation can always be is less than the amount of space initially performed. There is no way to remove available to them, each stack is able to an element from a queue containing no grow and shrink to any size elements, thus remove operation can be  No space has been pre-allocated to any applied only if the queue is non-empty. single stack and no stack is using space  The result of an illegal attempt to that it does not need. remove an element from empty queue is called underflow © Copyright Reserved by Gateflix.in No part of this material should be copied or reproduced without permission  2.2.2 LINKED IMPLEMENTATION OF information is needed in the array QUEUES implementation. [Note: The space used for a list node is  We know that, items are deleted from usually not twice the space used by an the front of the queue and inserted at array element, since the elements in the rear. Let a pointer to the first such a list usually consist of structures element of a list represent the front of with many subfields.] the queue and another pointer to the (ii) Additional time is needed in managing last element of the list represents the of available list. Addition and deletion rear of the queue as shown in Fig. 5 of each element from a stack or a queue illustrate the same queue after a new involves a corresponding deletion or item has been inserted. addition to the available list. Advantages: (i) All the stacks and queues of a program have access to the same free list of nodes. (ii) Nodes not used by one stack may be used by another, as long as the total number of nodes in use at any one time is not greater than the total number of nodes available. 2.2.3 PRIORITY QUEUE Fig 5: Queue after elements is inserted The result of its basic operation. The priority queue is a data structure in which  Under the list representation, a queue the intrinsic ordering of the elements of consists of a list and two pointers q determine Type of priority queue front and q rear. The operation empty  An ascending priority queue is a (q) and x = remove (q) are completely collection of items into which items can similar to empty (s) and x = pop (s). be inserted arbitrarily and form which with the pointer q front replacing s. only the smallest item can be removed.  Also, important consideration is  A descending priority queue is required when the last element is collection of items into which can be removed from a queue. In that case, q inserted arbitrarily and it allows rear must also be set to null, because in deletion of only the largest item. an empty queue both q front and q rear must be null. 2.2.3.1 Priority queue has following  Insert (q, x) is same as adding an rules: element x after the last element of list.  An element of higher priority is Disadvantages of representing a stack or processed before any element of lower queue by a linked list: priority.  Two elements with the same priority (i) A node in a linked list occupies more are processed according to the order in storage than a corresponding element which they were added to the queue. in an array, since two pieces of © Copyright Reserved by Gateflix.in No part of this material should be copied or reproduced without permission  2.2.3.2 Prototype of Priority Queue: the row that maintains the queue of elements with priority number K.  A prototype of a priority queue is a timesharing system: a program of high priority is processed first and programs with the same priority form a standard queue. 2.2.4 Representation of a Priority Queue: There are basically 2 different Fig 6: Array implementation of Priority representations of priority queue: Queue 1. One way list representation of a 2.2.4.3 List implementation priority queue 2. Array Representation of a Priority  An ordered list can be used to represent Queue a priority queue. For an ascending 3. List implementation of Priority Queues priority queue - (i) Insertion is implemented by place 2.2.4.1 One way list representation operation which keeps the list ordered. (a) Each node in the list will contain there (ii) Deletion of the minimum element is items of information: an information implemented by keeping the list in field INFO, q priority numbers PRN and descending rather than ascending a link number LINK. order. A priority queue (b) A node x precedes a node y in the list implemented as an ordered linked (i) When x has higher priority than y or list requires examining an average (ii) When both have the same priority of approximately n/2 nodes for but x was added to the list before y. insertion but only one node for Thus the order in the one-way list deletion. corresponds to the order of the priority  An unordered list may also be used as a queue. priority queue. Such a list require examining only one node for insertion 2.2.4.2 Array Representation but always requires examining n elements for deletion traverse the Another way to maintain a priority queue entire list to find the minimum or in memory is to use a separate queue for maximum and hen delete that node. each level of priority (or for each priority  Thus an ordered list is somewhat more number). Each such queue will appear in its efficient than an unordered list in own circular array and must have its own implementing a priority queue. pair of pointers. FRONT and REAR. In fact,  Advantages: List is somewhat more if each queue is allocated the same amount efficient than an array in implementing of space, a two-dimensional array QUEUE a priority queue. can be used instead of the linear arrays. A (i) No shifting of elements i.e. gaps is indicates this representation for the necessary in a list priority queue in b. Observe that FRONT[K] (ii) An item can be inserted into a list and REAR[K] contain, respectively, the without moving any other items, front and rear elements of row K of QUEUE, whereas this is impossible for an © Copyright Reserved by Gateflix.in No part of this material should be copied or reproduced without permission  array unless extra space is left on a particular piece of hardware or using a empty. particular software system. For example, we have already seen 2.3 DEQUEUE that the ADT integer is not universally implementable. Nevertheless, by specifying A de-queue is a linear list in which the mathematical and logical properties of elements can be added or removed at a data type or structure, the ADT is useful either end but not in the middle. guideline to implementers and a useful tool to programmers who wish to use the data type correctly. 2.4.1 Queue as an abstract Data type The representation of a queue as an abstract data type is straight forward. We use ectype to denote the type of the queue Fig 7: Pointers in de-queue element and parameterize the queue type  De-queue is maintained by a circular with ectype. array DEQUE with pointer LEFT and o Abstract typeset QUEUE RIGHT, point to the two ends of the de- (ectype): queue. o Abstract empty (q);  The condition LEFT = NULL will be used o QUEUE (ectype) q; to indicate that a de-queue is empty. o Post condition empty = = (Len (q) = 0);  An input-restricted de-queue allows o Abstract ectype remove (q); insertion at only one end of the list but o QUEUE (ectype) q; allows deletion at both ends of the list. o Precondition empty (q) = = FALSE; o Post condition remove = = first (q`);  An output-restricted deque allows deletion at only one end of the list but o q = = sub (q`, 1, len(q`)-1); o abstract insert (q, elt); allows insertion at both ends of the list. o QUEUE (ectype) q; o ectype elt; 2.4 Abstract Data Types o Post condition q = = q` + ; A useful tool for specifying the logical 2.5 PERFORMANCE ANALYSIS properties of a data types is the abstract data type, or ADT. Fundamentally, a data The space complexity of an algorithm is the type is a collection of values and a set of operations on those values. That collection amount of memory it needs to run to completion. The time complexity of an and those operations from a mathematical algorithm is the amount of computer time construct that may be implemented using a it needs to run to completion. Time particular hardware or software data structure. The term “abstract data type” Complexity: The time T(p) taken by a program p is the sum of the compile time refers to the basic mathematical concept and the run (or execution) time. The that defines the data type. compile time does not depend on the In defining an abstract data type as a instance characteristics. The runtime is mathematical concept, we are not denoted by TP (instance characteristics). concerned with space or time efficiency. To obtain such time at instance, we Those are implementation details. It may need to know that how many computations not concern to implement a particular ADT i. e. additions, multiplication, subtraction, © Copyright Reserved by Gateflix.in No part of this material should be copied or reproduced without permission  divisions performed by an algorithm. But 2.6 ASYMPTOTIC NOTATION (O, Ω, ) still obtaining correct formula for each (1) Big oh (O) algorithm is impossible task, since the time The function f(n) = O(g(n)) (read as f of n is needed for an addition, subtraction, big oh of g of n) iff exists positive constants multiplication and so on, often depends on c and n0, such that f(n) ≤ c* g(n) for all c, n the numbers being added, subtracted, and  n0. multiplied and so on. The value of Tp (n) for any given n can be obtained only For Example experimentally. The program is typed, complied and run on a particular machine. 1. The function 3n + 2 = O (n) as 3n + 2  The execution time is physically clocked 4n for all n  2. and Tp(n) is obtained. 2. The function 3n + 3 = O (n) as 3n + 3  We can determine the number of 4n for all n  3. steps needed by a program to solve a 3. The function 3n + 2  O (1) as 3n + 2 is particular problem instance in one of two not less than or equal to c for any ways- constant c and all n  n 0. (i) In the first method, we introduce a  We write O (1) to mean a computing new variable count into the time that is a constant, Similarly - program. This is a global variable  O(n) is called linear with initial value 0. Statements to  O(n2) is called quadratic increment count by the appropriate  O(n3) is called cubic amount are introduced into the  O(2n) is called exponential program. This is done so that each time a statement in the original  If an algorithm takes time O(log n), it is program is executed; count is faster, for sufficiently large n, than if it incremented by the step count of had taken O(n). Similarly O(n log n) is that statement. better than O(n2) but not as good as O(n). (ii) The second method to determine the step count of an algorithm is to  From the definition of O(Big-oh), it build a table in which we list the should be clear that f(n) = O(g(n) is not total number of steps contributed by the same as O(g(n)) = f(n). each statement. This number is often arrived at, by first determining  If f(n) = am nm +……+a1n + a0, then the number of steps per execution f(n) = O(nm) (s/e) of the statement and the total Proof: number of times (i. e. frequency) m F(n)   a i n i each statement is executed. The s/e i 0 of a statement is the amount by m which the count changes as result of  n m  a i n i m the execution of that statement. By i 0 m combining these two quantities the nm  ai for n  1 total contribution of each statement i 0 is obtained. By adding the so f(n) = O (nm) contributions of all statements, the step count for entire algorithm is 2.6.1 Omega (Ω) obtained. The function f(n) = Ω(g(n)) (read as f of n is omega of g of n) if there exist positive © Copyright Reserved by Gateflix.in No part of this material should be copied or reproduced without permission  constant C and n0 such that f(n) For example  C * g(n)for all n, n  n 0. 1. The function 3n + 2 = (n) as 3n +2 For example:  3n for all n  2&3n+2  4n for all n  n, 1. The function 3n + 2 = soC1 =3,C2 =4and n 0 =2 Ω(n)as3n+2  3n for n  1theinequality 2. The function 3n + 3 = (n) holdsfor n  0,but thedefinition of Ω  The theta notation is more precise both requires an n0 > 1. the big-oh and omega notations. The 2. The function 3n + 3  (n)as(3n  3)  3n forn  1. function f(n) = (g(n)) if g(n) is both on upper and lower bound on f(n). 3. The function 3n + 3 = Ω (1)  If f(n) = amnm+……..+ a1n + a0 and am> 0 then f(n) = (nm)  As in the case of big-oh notation, there are several functions g(n) for which f(n) 2.6.3 Little “Oh” (o) = Ω (g(n)). The function g(n) is only a lower sound on f(n). The function f(n) = o(g(n)) (read as f of n is f (n )  For the statement f(n) = Ω(g(n)) to be little oh of g of n) iff lim 0 n  g(n ) informative g(n) should be as large as possible function of n for which the For example: statement f(n) = Ω(g(n)) is true. 1. The function 3n + 2 = o(n2) since  So, when we say that 3n + 3 = Ω(n) 3n  2 lim 0 6  2 n  n 2  (2 n ) we almost never say n  n 2 that 3n + 3 = Ω(1) or 6  2n  n 2  (1) 2. The function 6  2 n  n 2  o(3n ) even though both of these statements are correct. 2.6.4 Little “omega” (ω)  if f(n) = amnm+………+a1n + a0 and am> 0 The function f(n) = ω(g(n)) (read as f of n is then f(n) = Ω(nm). g(n ) little omega of g of n) iff lim 0 n  f (n ) 2.6.2 Theta () The function f(n) = (g(n)) (read as f of n is theta of g of n) iff there exist positive constantC1, C2,andho such that C1g(n)  f (n)  C2g(n) for all n, n  n 0.` © Copyright Reserved by Gateflix.in No part of this material should be copied or reproduced without permission  3 SORTING & SEARCHING 3.1 SORTING Working: Sorting refers to the operation of arranging Bubble sort uses two counter i and j such data in some given order, such as that i begins with (n -2) and decrements till increasing or decreasing with numerical to 0. For every value of i, j begins with 0 data or alphabetically with character data. and goes upto i. A file of size b is a sequence of n items r, r,…….[n – 1]. Each item in the file is Example: called a record. A sort is internal if the records that If n = 5, then i ranges from (n-2) down to 0 it’s sorting are in main memory or external i.e. 3 down to 0 and for each value of i, j if some of the records that it’s sorting are in varies from 0 to i. auxiliary storage. A sorting technique is called stable if For (i=n-2; i>=0; i--) for all records i and j such that k[i] equals k[j], if r[i] precedes r[i] in the original file, For (j=0; j Efficiency Consideration: a [j + 1]) and if true, exchange a[j] with a [j + 1] There most important things that Hence determine the efficiency of sorting are: for(i= n -2; i>=0;i--) 1. Amount of time that must be spent by for (j = 0; j a[j + 1] ) sorting program. { 2. The amount of machine time necessary t = a[j]; for running the program. a[j] = a[j + 1]; 3. The amount of space necessary for the a[j + 1] = t; program. } 3.2 SORTING ALGORITHMS Let us show working with diagram. Let ‘a’ be array of 5 elements i. e. n = 5. 3.2.1 BUBBLE SORT In bubble sort, pass goes through the file sequentially, several times. Each pass consists of comparing each element in the file with its successor (x[i] with x[i + 1]) and interchanging the two elements if they are not in proper order. Algorithm Fig 1: Array during pass I Given Array `a` of `n` integers [0……..n-1] Aim : To sort `a` in ascending order. © Copyright Reserved by Gateflix.in No part of this material should be copied or reproduced without permission  X with (25 with 57) No interchange x X with (25 with 57) Interchange x X with (25 with 57) Interchange x  After the first pass, the file is in the order 25, 48, 37, 12, 57, 86, 33, 92 Fig 2: Array after pass I 2. After second pass: 25, 12, 37, 48, 57, 33, 86, 92 3. After Third pass: 25, 12, 37, 48, 33, 57, 86, 92 4. After Fourth pass: 12, 25, 37, 33, 48, 57, 86, 92 5. After Fifth pass: 12, 25, 33, 37, 48, 57, 86, 92 Fig 3: Array after pass II 6. After Sixth pass: 12, 25, 33, 37, 48, 57, 86, 92 7. After Seventh pass: 12, 25, 33, 37, 48, 57, 86, 92  After the nth pass, the nth largest element is in its proper position within the array. Fig 4: Array after pass III  The sorting method is called bubble sort because each number slowly “bubbles” up to its proper position.  As each iteration places a new elements into its proper position, a file of n elements requires not more than (n – 1) Fig 5: Array after pass IV iterations. Note: Bubble sort requires (n – 1) passes to sort array of `n` elements.  As all the elements in positions greater than or equal to (n – i) are already in proper position after the ith iteration, Example: they need not be considered in Consider the following file 25, 57, 48, 37, 12, 92, 86, 33 succeeding iterations. If the file can be sorted in fewer than (n -1) passes, the 1. First pass: final pass makes no interchanges. X with (25 with 57) No interchange x 3.2.1.2 Comparisons X with (25 with 57) Interchange x On the first pass (n – 1) comparisons are X with (25 with 57) Interchange made, on the second pass (n – 2) x comparisons and on the (n -1)th pass only X with (25 with 57) Interchange x one comparison is made. Thus there are (n © Copyright Reserved by Gateflix.in No part of this material should be copied or reproduced without permission  – 1) passes and (n – 1) comparisons on Quicksort (pivot, i, j) each pass. 1. Increment the value of i till Pivot > a[i] Total number of comparison=(n–1)*(n -1) 2. Decrement the value of j till Pivot  a[j] = n2 – 2n + 1 3. If i and j are not crossing each other, = O (n2) then interchange the values of i and j. 4. If i and j are crossing each other, then Note: It is the number of interchanges interchange the value of j with pivot. rather than the number of comparisons 5. Interchange of j with pivot, divide the that takes up most time in the program`s array into two unsorted array, one at execution. the left of pivot and one at the right of Now as all the elements in positions greater pivot. than or equal to (n– i) are already in proper 6. Apply the same rule on left and right position after iteration i, so they need not arrays to sort them and then merge the be considered in succeeding iterations. two to get final sorted array. Thus number of comparisons on iteration i 7. Example - is (n – i). If there are k iterations, the total (a) 34, 12, 67, 82, 90, 17, 42 number of comparisons is - (b) 34, 12, 17, 82, 90, 67, 42 =(𝑛– 1) + (𝑛 − 2) + (𝑛 − 3) + ⋯ + (𝑛 – 𝑘) (c) 17, 12, 34, 82, 90, 67, 42 = 𝑘𝑛 − [1 + 2 + 3 + 4 … … … … … … …. 𝑘)] Apply Quicksort (pivot, i, j) on Right = 𝑘𝑛 − [𝑘(𝑘 + 1)/2] sub-array 82, 90, 67, 42 2𝑛𝑘−𝑘2 −𝑘 (d) 82, 42, 67, 90 = (e) 67, 42, 82, 90 2 Thus bubble sort can be speed up by (f) 42, 67, 82, 90 considering (n – 1) comparisons on the Apply Quicksort (pivot, i, j) on Left sub- first pass, (n– 2) comparisons on the array 12, 17 second pass and only one comparison on (n Merge left and right sorted sub-arrays – 1)th pass. 12, 17, 34, 42, 67, 82, 90 Note: It is not necessary to choose the first 3.2.2 QUICK SORT elements as pivot, one can choose any item as Pivot. Quick sort works on Divide and Conquer policy. It is also called partition Exchange 3.2.2.1 EFFICIENCY Sort. Assume array size is n as a power of 2 i. e. n Divide: = 2m, so that m = log2 n. Also assume The array X[P…r] is partitioned into two proper position for the pivot always is the non-empty sub arrays X[p…q] and X[(q+1) middle of the sub array. …. r]. The index q is computed as part of Thus there will be n (actually n – 1) this partitioning procedure. comparisons on the first pass, after which the file is split into two sub array each of Conquer: size n/2. For each of these two arrays, The two sub arrays X[p….q] and X[(q + there are n/2 comparisons approximately 1)….r] are sorted by recursive calls to quick and thus a total of 2(n/2) comparisons. So sort after halving the sub array m times, there are n arrays of size 1. Example: Thus the total number of comparisons for Consider the following unsorted array the entire sort is approximately: 34, 42, 67, 82, 90, 17, 12 = n + 2*(n/2) + 4*(n/4) + 8*(n/8) + ……. + n* (n/n) © Copyright Reserved by Gateflix.in No part of this material should be copied or reproduced without permission  = n + n + n+………+n (m times) Thus total number of comparisons is O(n * m) or O(n log n). 3.2.3 SELECTION SORT Similarly all passes can be shown as follows- In selections sort successive elements are selected in order and placed into their proper sorted position. Selection sort consists of a selection phase in which the largest of the remaining element is repeatedly placed in its proper position, i. e. at the end of the array. This largest elements is interchanged with the element at the end of the array. Thus the initial n element priority 3.2.4 BINARY TREE SORT queue is reduced by one element after each Binary tree sort uses a binary search tree. It selection. Thus after (n – 1) selections the entire array would be sorted as selection involves scanning each element of the input process needs to be done only from (n – 1) file and placing it into its proper position in down to 1 rather than down to 0. a binary tree. To find that proper position of an element `a`, a left or a right branch is This method also requires (n – 1) passes for sorting array of n elements. For taken at each node, depending on whether Example, to sort array of 5 elements, a is less than the element in the node or greater than or equal to it. selection sort needs 4 passes. In pass As soon as the input elements are in number `i`, selection sort finds minimum elements between a[i] and a[n–1] (i. e. from their proper position in the tree, the sorted position i to n–1) and then interchange the array can be retrieved by an in order traversal of the tree. This has two phases. minimum element with a[i]. First phase is creating a binary search tree Let us show working of selection sort using diagrams. Let `a` be array of 5 using the given array elements. Second integers phase is to traverse the created binary Pass 0: Check minimum element between search tree in order thus resulting in a sorted array. a to a, which is a = -1 Interchange this minimum with a 3.2.4.1 Performance of the algorithm:  The array after pass 0 is The average number of comparisons for this method is O(n log2 n). but in the worst case, the number comparisons requires is O(n2), a case which arises when the sort tree is severely unbalanced. Pass 1: Check minimum elements between a to a[n-1] which is a=0 and interchange this with a. The array after pass 1 is- © Copyright Reserved by Gateflix.in No part of this material should be copied or reproduced without permission  e. g., Original data: 4, 8, 12, 17, 26. A heap is binary tree satisfying the In this case the insertion of the first node property: Every node has a greater value requires no comparisons, the second node than its child node. For a given unsorted requires two comparisons, and soon. Thus array, when a heap is formed, the element the total number of comparisons is at the root node is the largest element and n * (n  1) it is removed from the heap and placed at 2 + 3 +….+ n =  1 =O(n2) the end of the array. The element at the end 2 Example: of array which has been replaced by root Consider the following unsorted array node is placed at the root node and again (i) Construct a binary tree with shuffling a new heap is formed and the (a)Elements on left of node are smaller same process is repeated. At the end we are (b)Elements on the right of node are left with only one element in the heap and greater complete sorted array. (ii) Perform in order transversal of the tree The drawbacks of the binary tree to get sorted array. sort are remedied by the heap sort, an in (iii) place sort that requires only O(n log n) operations regardless of the order of the input. 3.2.5.1 Heap (or descending heap): A heap (descending heap) of size n can be defined as an almost complete binary tree of n nodes such that the contents of each node is less than or equal to the content of its father. If the sequential representation of an almost complete binary tree is used, this condition reduces to the inequality. A[j]  A[jdiv2]for1  (jdiv2), j  n. It is clear from this definition of a descending heap that the root of the tree (or the first element of the array) contains the largest element in the heap. We now 3.2.4.2 Comparison formulate an algorithm which will have as input an unsorted array and produce as If original array is completely sorted (or output a heap sorted in reverse order), then insertion of the first node requires no comparisons, the 3.2.5.2 Algorithm for creating a heap second requires two comparisons, the third node requires three comparisons and so 1. Repeat through step 7 while there is on. Thus the total number of comparison is another element to be placed in the n *(n  1) heap. 2 + 3 +…..+ n=  1= O(n2) 2 2. Obtain child to be placed at leaf level. 3.2.5 HEAP SORT 3. Obtain position of parent for this child. 4. Repeat though step 6 while the child Binary heap data structure is an array has a parent and the value of the child is those object that can be viewed as a greater than that of its parent. complete binary tree. 5. Move the parent down to position of child. © Copyright Reserved by Gateflix.in No part of this material should be copied or reproduced without permission  6. Obtain position of new parent for the child. 7. Copy child element into its proper position. 3.2.5.3 General algorithm for the heap sort 1. Create the initial heap. 2. Repeat through step 8 for n - 1 times. 3. Exchange the first element with the last unsorted element. 4. Obtain the index of the largest son of the new element. 5. Repeat through step 8 for the unsorted element in the heap and while the current element is greater than the first element. 6. Interchange the elements and obtain the next left son. 7. Obtain the index of the next left son. 8. Copy of the element into its proper Sort