ad a UOT " CHEAIIVITY a ey aaa NS PRINCIPLES a PARP Veatlelt ASA Era earsa yaaasca B oT SSCONVICTION CONFIDENC \ als Py ag a ug ceds af LEARN iL he Lhe = AUNT es SIICCESS FOUNDATION te Ae y-]es GAINS SATISEACTIO! RGN at Nilo) Vi WS ON YOUR MARK Petre LEADER ACTION PRUDENC! EDUCATION U TION te reyes: ates Tay. | SUCCESS GAINS ae petatis aed Coit NEVA Ray Pay Nite), eS Se QUESTION Paya o7VM: THOUGHTS CONVICTION | CU: pays rte As anette atau) alls iaeL feet EXPERTISE ee Eat ze Pile! VY Di yea A rel, Boh) folei tt a: Sem. Ill [Computer Group] | Data Structure Using ‘C’ Notes [CONTENTS Topic 1 Topic 2 Topic3 Topic 4 Topic 5 Topic 6 | Topic7 Syllabus duction to Data Structure 11 Basic Terminology ‘AZ _ Operations on Data Structures »T3 Different Approaches to Designing an Algorithm +4 — Complexity 15. Big’0' Notation Sorting and Searching ‘21 Sorting Techniques 1-22 Searching Stacks 3.1 Introduction to stack 3.2 Applications of Stack Queues 41 ~ Introduction 42 Types of Queue 43 Applications of Queue Linked List 5 Introduction 52 Type oflists 53 Operations on a singly linked list (only algorithm) Trees 6.1 Introduction 62 Type of Trees 63 Binary tree traversal (only algorithm) 64 Expression tree Graph and Hashing 7.1 Introduction 72 Representatiohs of a graph 7.3 Traversal of graphs 7.4 Applications of Graph 75 HashingData Structure using ‘C’ [DSU] SY. Diploma : Sem. I [CO/CMAF/CD/CW] EVALUATION SYSTEM Theory Exam Practical Exam [Oral Exam Term Work Sessional Work (Two Tests) @ - Internal Assessment, # - External Assessment SYLLABUS Topic -1 Introduction to Data Structure [8 marks] Specific Objective > To understand data structure organization & classification > To understand operations on data structure > To.understand approaches to design an algorithm > Knowing the complexity of an algorithm 1.1 Basic Terminology «Elementary data structure organization * Classification of data structure 1.2 Operations on Data Structures + Traversing, Inserting, deleting Searching, sorting, merging | 1.3 Different Approaches to Designing an Algorithm ' + Top-Down approach * Bottom-up approach 1.4 Complexity ‘© Time complexity © Space complexity 5 Big ‘0’ Notation - 0Topic -2 Topic -3 Sorting and Searching Specific Objective: > To understand and apply sorting algorithms on data. > To understand and apply searching algorithms on data. [16 marks] 2.1 Sorting Techniques * Introduction * Selection sort * Insertion sort * Bubble sort © Merge sort © Radix sort (Only algorithm) * Shell sort (Only algorithm) * Quick sort (Only algorithm) 2.2 Searching «Linear search * Binary search Stacks Specific Objective: > To understand and apply the knowledge of the data structure — ‘stack in the application programs. [18 marks] 3.1 Introduction to Stack © Stack as an abstract data type Representation of stack through arrays 3.2 Applications of Stack © Reversing a list- * Polish notations Conversion of infix to postfix expression Evaluation of postfix expression «Converting an infix into prefix expression « Evaluation of prefix expression « RecursionTopic -5 Topic -6 Queues [12 marks] Specific Objective : > To understand and apply the knowledge of the data structure — ‘Queue’ in the application programs. 4.1 Introduction © Queues as an abstract data type « Representation of a Queue as an array 4.2 Types of Queue ¢ Circular Queue * Double Ended Queue « Priority Queue * Dequeues 4.3 Applications of Queue Linked List Specific Objective: » To understand and apply the knowledge of the data structure — ‘Linked List’ in the application programs. [12 marks] 5.1 Introduction * Terminologies: node, Address, Pointer, Information, Next, Null Pointer, Empty list etc. 5.2 Type of lists ¢ Linear list «Circular list * Doubly list 5.3 Operations on a Singly Linked List (only algorithm) Traversing a singly linked list «Searching a linked list Inserting a new node in a linked list Deleting a node from a linked list Trees [18 marks] Specific Objective: » To understand and apply the knowledge of the data structure - ‘Trees’ on data. ily)Topic -7 6.1 Introduction * Terminologies: tree degree of a node, degree of a tree, level of a node, leaf node, Depth / Height of a tree, In-degree & out-Degree, Directed edge, Path, Ancestor & descendant nodes. 6.2 Type of Trees © General tree * Binary tree * Binary search tree (BST). 6.3 Binary Tree Traversal (only algorithm) « Inorder traversal * Preorder traversal * Post order traversal 6.4 Expression tree Graph and Ha Specific Objective: » To understand and apply the knowledge of ‘graph’ and ‘hashing’ function on data, [16 marks] 7.1 Introduction * Terminologies: graph, node (Vertices), arcs (edge), directed graph, in-degree, out-degree, adjacent, successor, predecessor, relation, weight, path, lenath, 7.2 Representations of a Graph «Array Representation « Linked list Representation 7.3 Traversal of Graphs * Depth-first search (DFS). * Breadth-first search (BFS). 7.4 Applications of Graph 7.5 Hashing * Hash function * Collision resolution techniques Qqo000 wwINTRODUCTION TO DATA STRUCTURE Baecisy Weightage : 8 Marks ISpecific Objective : > To understand data structure organization & classification > To understand operations on data structure > To understand approaches to design an algorithm > Knowing the complexity of an algorithm | [1.1 Basic Terminology 5 ij «Elementary data structure organization | Classification of data structure 1.2 Operations on Data Structures h, * Traversing, Inserting, deleting n, Searching, sorting, merging 11.3 Different Approaches to Designing an Algorithm Top-Down approach Bottom-up approach 1.4 Complexity * Time complexity «Space complexity 1.5 Big ‘O' Notation 1.1 Basic Terminology | 1.2 Operations on Data Structures 1.3 _ Different Approaches to Designing an Algorithm 1.4 Complexity 15 Big ‘O' Notation2|__Vidyalankar : S.¥. Diploma — DS 1.1 BASIC TERMINOLOGY Qi Ans.: Q2 Ans.: ‘What is the need for data structures? A data structure helps you to understand the relationship of one data element with the other and organize it within the memory. Sometimes the organization might be simple and can be very clearly visioned, for example, list of names of months in a year. We can see that names of months have a linear relationship between them and thus can be stored in a sequential location or in a type of data structure in which each month Points to the next month of the year and it is itself pointed by its preceding month. This principle is overruled in case of first dnd last month's names. Similarly, think of a set of data that represents location of historical places in a country (Fig.). For each historical place the location is given by country name followed by state name followed by city name, and then followed by the historical place name. We can see that such data form a hierarchical relationship between them and must be represented in the memory using a hierarchical type of data structure. India UP Delhi Maharashtra / Ag Rey Qutub Mumbai Fort Minar Taj Mahal Gateway of India The above two examples clearly identify the usefulness of a data structures. A data structure help you to analyse the data, store it and organize it in a logical or mathematical manner. Explain what is Abstract Data Type (ADT)? An Abstract Data Type (ADT) is defined as a mathematical model of the data objects that make up a data type as well as the functions that operate on these objects. An abstract data type is the specification of logical and mathematical properties of a data type or structure. ADT acts as a useful guideline to implement a data type correctly. The specification of an ADT does not imply any implementation consideration. The implementation of an ADT involves the translation of the ADT's specification into syntax of a particular programming language, The important step is the definition of ADT that involves mainly two parts: (i) Description of the way in which components are related to each other 989499699 469499999 OP99999599 99779 XK hbQ3 Ans.: Topic 1: Introduction to Data Structure | 3 (ii) Statements of operation that can be performed on that data type. For example, the int data type, available in the ‘C’ programming language provides an implementation of the mathematical concept of an integer number. The int data type in ‘C’ can-be.considered.as an implementation of Abstract Data Type, INTEGER-ADT. INTEGER-ADT defines the set of numbers given by the union of the set {-1,--2, -3...0} and the set of whole numbers {0; 1.... + 0}. INTEGER-ADT also specifies the operations that can be performed on an integer number, for example, addition, subtraction, multiplication, etc. In the specification of the INTEGER-ADT, following issues must be considered: * Range of numbers that will be represented. © Format for storing integer numbers. This determines the representation of a signed integer value. Explain the classification of Data Structures. [W-14, 16] Classification: Data structure is broadly classified into two categories: 1. Primitive data structures. 2. Non-primitive data structures. A detailed data structure classification is shown in the Fig. Primitive Data Structure These data structures are basic structures and are manipulated / operated directly by machine instructions. We will present storage representations for these data structures for a variety of machines. The- integers floating-point numbers ~(real numbers), character constants, string constants, pointers etc. are some of the primitive data structures. In C language, these primitive data structure are defined using data types such as int, float, char and double. But you are already aware of these representation in computer main memory. Fig. : Data structure classifications4| 12 Qi Ans.: Vidyalankar: S.. Diploma - DS Non-primitive Data structure These data structures are more sophisticated and are derived from the primitive structures, But, these cannot be manipulated / operated directly by machine instructions. A nor.-primitive data structure emphasize on structuring of a set of homogeneous (same data type) or heterogeneous (different data types) data elements. Arrays, structures, stacks queues linked lists, flies etc, are some of the non-primitive data structures, The non-primitive data structures are again classified into linear data structures and non-linear data structures, Data structures which shows the Telationship of adjacency between elements is said to be linear data structures; any other data structure is said to be non-linear data structure, A linear data structures is classified into stack, queue, linear linked lists such as} singly linked list, doubly linked linear list etc. and non-linear data structure are trees, graphs and files, etc * Our aim is study the above-mentioned data structures and its operations. Each data structure categorized into individual chapters. Each chapter Contains data structure's description, operations, display of data structure Contents with examples using C language. OPERATIONS ON DATA STRUCTURES Explain the various operations on Data Structures. [W-14, 15; $-16] Data structures are used for the storage of data in computer so that data can be used efficiently. The data manipulation within the data structures are performed by means of certain operations. In fact, the particular data structure that one chooses for a given situation depends largely on the frequency with which specific operations are performed, The following six operations play a major role on data structures, (i) Traversing : Accessing each record exactly once so that certain items in the record may be processed, (This accessing and processing is sometimes called “visiting” the record.) Searching : Finding the location of the record with a given key value, or finding the locations of all records, which satisfy one or more conditions. i) Inserting : Adding a new record to the structure. (iv) Deleting : Removing a record from the structure. Sometimes two or more of these operations may be used in a given situation. For example, if we want to delete a record with a given key (iirr Topic 1 : Introduction to Data Structure | 5 value, at first we willl have need to search for the location of the record and then delete that record. (v) Sorting : Operation of arranging data in some given order, such aS increasing or decreasing, with numerical data, or alphabetically, with character data. (vi) Merging : Combining the records in two different sorted files into a single sorted file 1.3 DIFFERENT APPROACHES TO DESIGNING AN ALGORITHM. Q1 Explain the top-down approach and bottom-up approach in algorithm design. Ans.: Different Approaches to Designing an Algorithm —_[S-14, 15; W-14] A complex system may be divided into smaller units called modules. The advantage of modularity is that it allows the principle of separation of concerns to be applied into two phases: when dealing with detail of each module in isolation (ignoring details of other modules) and when dealing with overall characteristics of all modules and their relationships in order to integrate them into a system. Modularity enhances design clarity, which in turn eases implementation, debugging, testing, documenting and maintenance of the product. A system consists of components, which have components of their own, Indeed a system is a hierarchy of components. The highest level component corresponds to the total system. To design such a hierarchy there are two possible approaches: * Top-down approach * Bottom-up approach Top-Down Approach A top-down design approach starts by Identifying the major components of the system or program, decomposing them into their lower-level components and iterating until the desired level of module complexity is achieved. Top-down design method takes the form of stepwise refinement. In this, we start with the topmost module and incrementally add modules that it calls, Thus, in top-down approach we start from an abstract design. In each step, design is refined into most concrete level until we reach the level where no more refinement is needed and the design can be implemented directly,6 | Vidyalankar : S.¥. Diploma - DS Bottom-Up Approach A bottom-up design approach starts with designing the most basic or primitive components and proceeds to higher-level components. Bottom- up method works with layers of abstraction. Starting from the very bottom, the operation that provide a layer of abstraction are implemented. The operations of this layer are then used to implement more powerful operations and still higher layer of abstraction, until the stage is reached where the operations supported by the layer are those by the system. - Q2 Describe Top-down and bottom-up approach by giving example. [W-15] Ans.: Refer Answer of Q.1 Q3 Compare Top-down approach v/s Bottom-up approach [any four points] [W-16] Ans.: Refer Answer of Q.1 1.4 COMPLEXITY Q1 Explain the concept of Time Complexity and Space Complexity. {W-13, 15; S-14, 15] Ans. The analysis of the program requires two main considerations: Time complexity © Space complexity The time complexity of a program / algorithm is the amount of computer time that it needs to run to completion. The space complexity of a program/algorithm is the amount of memory that it needs to run to completion. Time Complexity [W-16] While measuring the time of an algorithm, we concentrate on developing ‘only the frequency count for all key statements (statements that are important and are the basic instructions of an algorithmn), This is because, it is often difficult to get reliable timing figure because of clock limitati : ‘and the multiprogramming or the sharing environment, “Hd roe 4 9775 Da aa DED DTD ATA DD DDDRAARADODODMDTopic 1: Introduction to Data Structure | 7 Consider the algorithm given below: ALGORITHM a=a+l A forx = 1 ton step 1 ALGORITHM ail 8 Loop forx=1tonstep1 ALGORITHM fory =1ton step 1 iG a=a+l Loop In the algorithm A we may find that the statement a = a + 1 is independent and is not contained within any loop. Therefore, the number of times shall be executed is 1. We can say that the frequency count of algorithm A is 1 In the second algorithm, i.e. B, the key statement out of three statements. is the assignment operation a = a + 1, Because this statement is contained within a loop, the number of times it is executed is n, as the loop runs‘for n times. The frequency count for this algorithm is n. According to the third algorithm, the frequency count for the statement a= a+ 1isn’as the inner loop runs n times, each time the outer loop runs, the outer loop also runs for n times. n? is said to be different in increasing order of magnitude just like 1, 10, 100 depending upon the n, Space Complexity [W-16] The space needed by the program is the sum of following components; Fixed space requirement This includes the instruction space, for simple variables, fixed size structured variables and constants, Variable space requirement This consists of space needed by structured variables whose size depends on particular instance of variables. It also includes the additional space required when the function uses fecursion,8| _ Vidyalankar: S.V. Diploma - DS 1.5 BIG ‘O’ NOTATION Qi Ans.: Q2 Ans.: Describe the Big ‘0’ notation. [S-14) Big ‘O' Natation If f(n) represents the computing time of some algorithm and g(n) Tepresents a known standard function like n,n’, n log n, etc. then to write, f(n) is 0 g(n) Means that f(n) of n is equal to biggest order of function g(n). This implies only when: If (n)! < Clg(n)! for all sufficiently large integers n, where C is the constant whose value depends upon various factors discussed above. From the above statements, we can say that the computing time of an algorithm is O (g(n)), we mean that its execution takes no more than a constant time g(n). n is the parameter which characterizes the input and / or outputs. For example, n might be number of inputs or the number of outputs or their sum or the magnitude of one of them. If analysis leads to the result f(n)=0 (g(n)), then it means that if the algorithm is run on the same computer on some input data for sufficiently large values of n, then the resulting computation time will be less than some constant time Ig(n)I. Why Big ‘0’ Notation Big O notation helps to determine the time as well as space complexity of the algorithms. Using the Big O notation, the time taken by the algorithm and the space required to run the algorithm can be ascertained. This information is useful to set the prerequisites of algorithms of algorithms and to develop and design efficient algorithms in terms of time and space complexity. 4TERLEDAAB The Big ‘O' Notation has been extremely useful to classify algorithms by their performances. Developers use this notation to reach to the best solution for the given problem, For example, for the quick sort algorithm the worst case complexity is O(n’) whereas for Bubble sort the average case complexity is O(n’). Thus, Quick sort can be graded as the better algorithm for sorting by any developer who has choice between the two. Define Big ‘O' Notation, [W-16] Refer Answer of Q.1 QaqQ00 ae222R22DTopic SORTING AND SEARCHING Bs Weightage : 16 Marks Specific Objective: > To understand and apply sorting algorithms on data > To understand and apply searching algorithms on data, 2.1 Sorting Techniques Introduction © Selection sort Insertion sort Bubble sort Merge sort Radix sort (Only algorithm) Shell sort (Only algorithm) Quick sort (Only algorithm) 2.2 Searching Linear search «Binary search Topic: 2.1 — Sorting Techniques 2.2 Searching10|_Vidyalankar:: $.Y. Diploma - DS 2.1 SORTING TECHNIQUES Qi Ans.: Q2 Ans.: Q3 Ans.: What is Sorting? What are its types? Sorting refers to the operation of arranging a set of data in some given order. A collection of records is called a list where each record contains one or more fields. The field, which contains Unique value for each record is known as the key field. For example, a telephone directory can be Considered as a list where each record has three fields-name, address and Phone number, Being unique, phone number can work as a key to locate any record in the list, Sorting is the operation of arranging the records of a table in some order according to an ordering criterion. Sorting is performed according to the key value of each record. The records are sorted either numerically or alphanumerically. The records are arranged in ascending or descending order depending on the numerical value of the key. For example, sorting of a list of marks obtained by a student in the class, The methods of sorting can be divided into two categories: * Internal Sorting * External Sorting Internal Sorting If all the data is to sorted can be adjusted at a time in main memory, then internal sorting methods are used. External Sorting When the data to be shorted can't be accommodated in the memory at the same time and some has to be kept in auxiliary memory (hard disk, floppy, tape, etc.) then external sorting methods are used, What is sorting? Enlist two categories of sorting. [W-15] Refer Answer of Q1 Explain Selection Sort with Algorithm and C Program. [S-15] Selection Sort The selection sort is the easiest method of sorting, In this, to sort data, in ascending order, the 0" element is compared with all other elements. If the 0" element is found to be greater than the compared element then they are interchanged. In this way, after the first iteration, the smallest element is placed at 0" position, The procedure is repeated for 1* element and so on.et Topic 2 : Sorting and Searching _| 12 Algorithm for Selection Sort: The following are the steps involved in the sorting process. Let L be an unordered list of elements A1, A2.....An, Step 1: In the first pass find the position POS of the smallest element in the list of n elements. Then swap POS with the first element of the list so that the first smallest element acquires its right position, ie. first position in the list. Step 2 : In the second pass find the position POS of the second smallest element in the list of n-1 elements. Swap POS with second element of the list. Step n : In the (n-1)th pass excluding the first two elements in the list repeat the sorting process by finding the next smallest element and swap it with an appropriate element until the entire list is sorted. The entire sorting takes (n-1) passes. To find the smallest element among all the elements in the list, first the variable SMALL is set to the first element of the list and the variable POS is set to the position of the first element and then traversing the list comparing SMALL with every other element of DATA\i] as follows: 1, If SMALL < DATAIi], then move to the next element 2. If SMALL>DATAIi], then update SMALL and POS as SMALL=DATALi] and PO! After comparing all the elements SMALL contains the smallest among all the elements and POS contains its location. C Program for Selection sort: #include #include void main() { int array[100], n, c, d, position, swap; printf("Enter number of elements:"); scanf("%d", &n); Printf("Enter %d integers:\n", nj;12 | Vidyalankar:S.Y. Diploma DS for(c=0; array[{d] ) position = d; ) if (position != c) { swap = array/c]; arraylc] = arraylposition|; arraylposition] = swap; } } print{('Sorted list in ascending order\n’); for (c= 0; c #include void main() {14|_Vidyalankar : $.Y. Diploma - Ds es teal z $$ _____ intn, array(100}, ¢, d, t printf("Enter number of elements:"); scanf(" &n); printf("Enter %d integers\n*, n); for (C= 0; c< { scanf("% C++) &array{c)); for(c=1; ¢<=n-1; c++) { while (d > 0 && array[d] < arrayld-1)) { t = arrayld}; array(d) = array{d-1); array(d-1) = t; d-- } printf("Sorted list in ascending order.\n"): for(c=0; ¢<=n-1; c++) { printf("%d\n", arraylc); ) getchd); ) Complexity of Insertion Sort If the initial file is sorted, only one comparison is made on each iteration, 50 that the sort is O(n). If the file is initially sorted in the reverse order the worst case complexity is O(n’). Since the total number of comparisons are: (nel) + (0-2) +... #34241 = (n-1)* n/2 which is O(n’)Q7 Ans.: Topic 2: Sorting and Searching | 15 Explain Bubble Sort with Algorithm and C Program. Bubble Sort In this sorting method, to arrange elements in ascending order, we begin with the 0" element and compare it with the 1" element. If it is found to be greater than the 1* element, then they are interchanged. In this way all the elements are compared (excluding last) with their next element and are interchanged if required. On completing the first iteration, the largest element gets placed at the last position. Similarly, in the second iteration second largest element gets placed at the second last position and so on. Asa result, after all the iteration’s, the list becomes a sorted list. Algorithm for Bubble Sort: Let L be an unordered list with elements Al, A2, A3......An. Bubble sort ordered these elements in their increasing order, that is L = {A1, A2, A3....., An}, where Al < A2 #include void main () { int array[100], n, ¢, d, swap; printf("Enter number of elements:”); scanf("%d", &n); printf("Enter %d integers\n", n);16 |_Vidyalankar : S.Y, Diploma - DS for (C= 0; c array[d+1)) { swap = array[d); array[d) = array[d+1); array[d+1] = swap; } } printf("Sorted list in ascending order.\n"); for (c=0; c #include void merge(int [ J,int int int); void part(int [int ,int ); void main() ( int arr{100}; int i,size; printf("Enter total no, of elements ; "); scanf("%d" &size); for{i=0; imid) { for(k=m; k<=max; k++) { tmp[i]=arr{k];Topic 2: Sorting and Searching {19 Q9 Ans.: its; } } else { for(k=j; k<=mid; k++) { tmpli=arr[k}; ise; } } for(k=min; ke=max k++) arr{k]=tmp|Ki; Complexity of Merge Sort: For Best Case - O (n log n) For Worst Case - O (n log n) For Average Case - 0 (n log n) Explain Radix Sort with Algorithm. The, radix sort is used generally when we intend to sort a large list of names alphabetically. Radix in this case can be 26, as there are 26 alphabets. Therefore, if we want to arrange a list or names we can classify the names into 26 classes, where the first class consists of those names starting with ‘A’. The second class consists of names starting with ‘8’ and soon. All this can be done in first iteration. In the second iteration each class is alphabetized according to the second letter of the name, and so on. The radix sort is based on the values of the actual digits in the positional Fepresentation. For example, the number 235 in decimal notation is written with a 2 in a hundred’s position, 3 in ten's position and 5 in the unit's position. The sorter used above uses decimal numbers where the radix is 10 and hence uses only the first 10 pockets of the sorter. Suppose we want to sort the following set of three digits numbers:20| Vidyalankar : $.¥, Diploma - DS 242, 986, 504, 428, 321 Pockets puts oft [2 [3 Ja |s fo |r Ja Jo ma 20 a6 7 304 308 an fe a RI par Pockets Fis erton tpus Jo 1 |2 |s Ja fs Jo |r Ja Jo on 428 8 86 ‘So [s0 me En Rr Br ‘Second iteration Pockets Yours ofr 2 fs fs |s Jo |r |e Jo 986, | 986 ey 2 a aa Rr RL Soe En Third iteration Fig. : Radix Sort The sorter list is as follows : [986 [504 | 428 321 242 Algorithm for Radix Sort 1. In the First iteration the elements are picked up and kept in various pockets checking their unit's digit. 2. The cards are collected from pocket 9 to pocket 0 and again they are given as input to sorter. 3. In second iteration the ten's digits are sorted, 4, Repeat through step 2. 5. In the final iteration (in the above example) the digits at hundred's position are sorted. 6. Repeat through step 2. The time requirement for radix sort method depends on the number of Complexity of Radix Sort digits and the number at elements in the file. The loop is traversed, forQ.10 Ans.: Ql Ans.: Topic 2: Sorting and Searching | 2. each digit (m times) and the inner loop is traversed (n times) for each element in the file the sort is approximately 0(m*n). The m approximates logn so that 0(m*n) approximates to 0(n log n). Note: C Program is not expected for Radix Sort in the Syllabus. Sort following elements by Radix sort algorithm. [w-16] 87.3, 2.34, 7.29, 3.59, 45.8, 3.79, 3.20, 422 Refer Answer of Q.9 Explain Shell Sort with Algoritim. Shell Sort This method is a improvement over the simple insertion sort. In this method the elements at fixed distance are compared. The distance will then be decremented by some fixed amount and again the comparison will be made. Finally, individual elements will be compared. Let us take some example. Example : If the original file is O11} aid Smee ee eee emee xery| 25 | s7 | 48 | 37 | 12 | o | a6 | 3 Step 1: Let us take the distance k = So in the first iteration compare (x [0], x{5]) (x (11, x (6) (x (2), x (7) (x(3)) (x{4) ic. first iterationDE a... 22| Vidyalankar:: s.y, Diploma - DS Step 2: Initially K was 5, Take some d and decrement K by d. Let us take d=2 i K=K-dieK=5-2=3 So now compare (3f0) x{{31, x16), (11, x14}, x17) (21, x15) Second iteration Step 3:NowK=K-d.K=3-2=1 So now compare (s{01, xf], x12], x{3], x14], x{5], x{6), x(7]) This sorting is then done by simple insertion sort. Because simple insertion Sortis highly efficient on sorted file. So we get Algorithm for Shell Sort 1. In the first iteration, the elements are splitted with a gap or say, 5, 3, etc. and are sublisted, 2. The sublist obtained after splitting is again sorted, 3. The sorted sublist is recombined, 4, The sorted list, in the second iteration, is again sublisted with a gap (here, itis 3), 5. Repeat through steps 2 and 3, Complexity of Shell Sort: Best Case - 0 (n) Worst Case - 0 (n log n*) Average Case ~ O (n log n*)Topic 2: Sorting and Searching | 23 Q.12 Explain Quick Sort with Algorithm. [S-14] Ans.: Quick Sort Quick sort is a very popular sorting method. It was introduced by Haore in 1962. It is a very important method of internal sorting. According to this algorithm it is faster and easier to sort two small arrays than one larger one. The strategy that quick sort follows is of divide and conquer. In this approach, numbers are divided and again subdivided and division goes on until it is not possible to divide them further. The procedure it follows is of recursion. Example Quick Sort : Let us take few elements and them in the array ‘ feos [sel ea [eee al LeToTeT=[ol[a tu Ts | Step 1: Set the a[0]" element ie. 25 as pivot element. The index 0 of array ais lower bound and the index 7 is the upper bound, ¥ ” OPA aI Ta a) ste [ow Ts |e Tow Tow Ts | 1 Now finda the element lesser than 25 and place 25 after all the lesser elements ‘Sutat | ‘Sublist 2 Prot Step 2: As in sub-list 1 only one element is present no need to sort it. But the sublist 2 can be sorted, For that purpose now set new pivot element as 57. Find all the lesser than 57 elements and place them before 57 Step 3: As again from sublist 1 and sublist 2 sort the elements take sublist 1, 48 is new pivot element place all lesser than 48 elements before \q Sota Swett? a oe is ln ow 1p io ‘ha the pivot 10 positon » 2 @ « @| 24| Vidyalankar : $.Y. Diploma - DS | Sublist 1 Pivot sorted list will be ‘Thus the list is sorted by quick sort. emay- 0 | ° 1 2 2 4 5 7 0 ESS w | 7 a 1 Algorithm 1. Read the total number of elements in the list say n. 2. Store the elements in the array. 3. Take the first element from the array and call it as the pivot element. 4, Now find all the elements which are less than this pivot element and place them before the pivot element. Thus the array will be divided in the lesser elements, pivot element and elements greater than the pivot element. 5. Repeat the step 4 each time placing the pivot element at its proper position. Thus the complete list will get sorted. 6. Stop. Complexity of Quick Sort: Best Case — O(n log n) ‘Average Case — O(n log n) Worst Case — O(n’)Q13 Ans.: Qua Ans.: Topic 2 : Sorting and Searching _| 25 Complexity Cheat Sheet Array Sorting Algorithms Algorithm Time Complexity Best Average Worst Quicksort o(n log (n) _| o(n log (n)) o(n’2) Mergesort o(n log (n)) __| o(n log (n)) o(n log (n)) Bubble Sort o(n) o(n’2) o(n’2) Insertion Sort o(n) o(n*2) o(n*2) Selection Sort o(n2) ‘o(n2) o(n’2) Shell Sort o(n) al(nloginy)*2)_[ o((nlogin))*2) Radix Sort o(nk) ‘o(nk) ‘o(nk) Describe quick sort. State its advantages and disadvantages. [W-15] Refer Answer of Q.12 Explain working of quick sort with a suitable example. [S-16] Refer Answer of Q.12 2.2 SEARCHING Qu Ans.: What is searching? Explain Linear Search in detail with C Program. Searching - An Introduction : [W-16] We often spend time in searching for the desired item. If the data is kept properly in sorted order, then searching becomes very easy and efficient. Searching is an operation which finds the place of a given element in the list. The search is said to be successful or unsuccessful depending upon whether the element that is being searched is found or not. Some of the standard.searching methods are discussed below. Linear or Sequential Search This is the simplest method for searching. In this method, the element to be found is searched sequentially in the list. This method can be used on a sorted or an unsorted list. In case of a sorted list searching starts from 0" element and continues until the element is found or the element whose value is greater than (assuming the list is sorted in ascending order) the value being searched is reached. As against this, searching in case of unsorted list starts from the 0" element and continues until the element is found or the end of list is reached.26 | Vidyalankar : Y. Diploma - DS For example, [evo |e) [pom ata The list given above is the list of elements in an unsorted array. The array contains 10 elements. Suppose the element to be searched is 46. So 46 is compared with all the elements starting from the 0" element and searching process ends where 46 is found or the list ends. The performance of the linear search can be measured by counting the comparisons done to find out an element. The number of comparisons is O(n). C Program for Linear Search: #include #include void main() { int array[100}, search, cn; printf("Enter the number of elements in array:"); scanf("%d",8n); printf("Enter 9d integers:\n", n); for (¢ = 0;¢ #include void main() { int ¢, first, last, middle, n, search, array[100]; printf("Enter number of elements:");28 Vidyalankar :S.Y. Diploma - DS scanf("%d" Bun); printf("Enter 9d integers\n", n); for (c = 0; ¢ last) printf("Not found! %d is not present in the list.\n", search); getch(); ) Complexity of Binary Search is O(log n). Q.3 Describe binary search algorithm. Give example to search at using binary search algorithm. Ans.; Refer Answer of Q.2 ggggaSTACKS Weightage : 18 Marks Specific Objective: » To understand and apply the knowledge of the data structure - ‘stack’ in the! application programs. Introduction to Stack * Stack as an abstract data type + Representation of stack through arrays 3.2 Applications of Stack «Reversing a list Polish notations Conversion of infix to postfix expression Evaluation of postfix expression Converting an infix into prefix expression Evaluation of prefix expression Recursion 3.1 Introduction to Stack 3.2 Applic ins of Stackee 30] Vidyalankar : S.Y. Diploma ~ DS 3.1 INTRODUCTION TO STACK Qu Ans.: Q2 Ans.: What are stacks? Explain stack as an Abstract Data Type (ADT)? Introduction to Stacks The linear data, structures-linked lists and arrays-allow us to insert and delete elements at any place in the list, at the beginning, at the end, or in the middle. In computer science we may come across situations, where insertion or deletion is required only at one end, either at the beginning or end of the list. The suitable data structures to fulfill such requirements are stacks and queues. A stack is a linear structure in which addition or deletion of elements takes place at the same end. This end in often called the top of stack. For example, A stack of plates, a stack of coins, etc. As the items in this type of data structure can be added or removed from the top, it means the last item to be added to the stack is the first item to be removed. Therefore stacks are also called Last In First Out (LIFO) lists. Stack as an Abstract Data Type [W-13; $-15] Stacks can also be defined as Abstract Data Types (APT). A stack of elements of any particular type is a finite sequence of elements of that type together with the following operations: (i) Initialize the stack to be empty. (ii) Determine whether stack is empty or not. (iii) Determine if stack is full or not. (iv) If "Stack is not full, then add or insert a new node at one end of the stack called top. This operation is called push, (v) If the stack is not empty, then retrieve the node at its top. (vi) If the stack is not empty, then delete the node at its top. This is called pop. The above definition of stack produces the concept of stack as an abstract data type. The basic operations that can be performed on stacks are-push and pop. Explain how stacks can be represented using Arrays. Representation of stacks Through Arrays Stacks can be represented in the memory through arrays. To do job we maintain a linear array STACK, a pointer variable TOP which contains the location of top element. The variable MAXSTACK gives the maximum number ‘of elements held by the stack. The TOP = 0 or TOP = NULL will indicate that the stack is empty.Q3 Ans.: Q4 Ans.: Topic3: Stacks | 32. Figure shows array representation of a stack. The top is pointing to 3 which says that stack has three items and as the MAXSTACK = 8, there is still space for accommodating five items. a [ew — + AH ca J Pry Array representation of a stack The operation of adding (pushing) an item onto a stack and the operation of removing (popping) an item can be implemented using the PUSH and POP functions. [Note: Sometimes when a new data is to be inserted into a data structure but there is no available space; the situation is called OVERFLOW. On the country, if one wants to delete data structure that is empty then the situation is called UNDERFLOW,] Describe the representation of stack using arrays. [W-15] Refer Answer of Q.2 Write the procedure for implementing stack using arrays. _[S-16] Refer Answer of Q2 3.2 APPLICATIONS OF STACK qu Ans.: Explain how to reverse a list using Stacks. Reversing a List fab Ainomyseck Lay Yew : r 7 A simple example of stack ie aN application is reversal of a [zl ms given fist. We can accomplish * this task by pushing each character onto the stack as it is read, When the line is PEPE — SB 5) finished, characters are then = ld wohl popped off the stack-they 3 € come off in reverse order as * EY shown in Fig, eS) hand E az mae 2 He Fat ine32| Vidyalankar : S.Y. Diploma - DS Q.2 Explain how stack can be used to reverse a list using suitable example. [S-16] Ans.: Refer Answer of Q.1 Q.3 How stack is useful in reversing a list? Write a C program to reverse a list using stack, [W-16] Ans.: Refer Answer of Q.1 Q4 Explain Polish Notations with Example. Ans.: Polish Notations The process of writing the operators of an expression either before their operands or after them is called the Polish Notation. This notation was introduced by Jan Lukasiewicz. The main property of Polish Notation is that the order in which operations are to be performed is ascertained by the position of the operators and operands in the expression. The computer system can understand and work only on binary paradigm, it assumes that an arithmetic operation can take place between two operands only. For example - A+B, CxD, D/A, etc, Usually an arithmetic expression may consists of more than one operator and two operands for example* (A+B) x C(D/UJ+D)). These complex arithmetic expressions can be converted into polish strings using, stacks which can then be executed in two operands and an operator form. The notation refers to these complex arithmetic expressions in three forms: ‘If the operator symbols are placed before its operands, then the expression is in prefix notation. ¢ If the operator symbols are placed after its operands, then the expression is in postfix notation. * If the operator symbols are placed between the operands then the expression is in infix notation, For example, Table : Notations Infix Notation Prefix Notation | Postfix Notation | A+B + AB JAB + (A-C)*B ACB JAC - B* lA +(B*C) + A* BC JBC (A+B) /(C-D) / + ABCD [AB + CD—/ (A +(B*O)/(C-(0*8) / + A*BC-C*DB__|ABC* + CDB + ~/Q5 Ans.: Topic 3: Stacks | 33 Explain how to convert an Infix Expression to a Postfix Conversion of Infix to Postfix Expression While evaluating an_ infix expression, there is an evaluation order according to which the operations are executed: Expression. * Brackets or Parentheses * Exponentiation * Multiplication or Division * Addition or Subtraction The operators with the same priority (e g.* and /) are evaluated from left to right. The steps to convert infix expression to Postfix expression are as follows: (i) The actual evaluation is determined by inserting braces. (ii) Convert the expression in the innermost braces into postfix notation by putting, the operator after the operands. (iii) Repeat the above step (ii) until the entire expression is converted into postfix notation. Algorithm to Convert Infix Expression to Postfix Expression The algorithm transforms the infix expression A into equivalent postfix form B. The algorithm uses stack to temporarily hold operators and left parentheses. The postfix expression B will be constructed left to right using operands from A and operators which are removed from STACK We begin by pushing left Parenthesis onto STACK and adding a right parenthesis at the end of A. The algorithm is finished when STACK is empty. The algorithm is as follows: (i) Push left parenthesis “(" onto STACK and add tight parenthesis *)" to the end of A (ii) Scan A from ieft to right and repeat steps 3 to 6 for each element of A until the stack is empty, (iii) If an operand is encountered, add it to B. (iv) Ifa left parenthesis is encountered push it onto the stack. (v) Ifan operator is encountered then (@) Repeatedly pop from the STACK and add to B each operator (on the top of stack) which has the same precedence as or higher precedence than operator. (b) Add operator to STACK, (vi) If right parenthesis is encountered, then: (a) Repeatedly pop from the STACK and add to B each operator (on the top of STACK) until a left parenthesis, is encountered, (b) Remove the left parenthesis. (Do not add left parenthesis to B) (vil Exita ee a 34 Vidyalankar : S.Y. Diploma - DS Example of conversion from Infix Expression to Postfix Expression: For example, consider the following arithmetic infix expression. PO 8 #6 mslecOa/ Gea tan) Ga SU) 12345 67 8 9 101112 13 14 15 16 17 18 19 20 A:A+(B*C-(D/ETF)*G)*H) The elements of A have now been labeled from left to right for easy reference. Table shows the status of STACK and of the Postfix string B as each element of A is scanned. (i) Each element is simply added to B and does not change STACK. (ii) The subtraction operator (-) in row 7 sends* from STACK to P before it (-)is pushed onto the STACK. (iii) The right parenthesis in row 14 sends * and then / from STACK to B, and then removes the left parenthesis from the STACK. {iv) The right parenthesis in row 20 sends * then + from STACK to B and then removes the left parenthesis from the top of STACK. After step 20 is executed the stack is empty. Table : Evaluation of an Expression from Infix to Postfix using Stack [Symbol Scanned Stack Expression 1) | A ( A. 2) | + (+ A 3) | ¢ (+ ( lA la) [8 (ex AB 5) | * a [AB l) [Cc (eG ABC 7) | = (FE [ABC * a) | ( [ABC* i) | D (4 (=( {asc*D 10) [7 GE JABC*D. laa) | E +E JABC*DE 2) | F (et |ABC*DE fe 13) | F (ACUTE JABC*DEF 14) |) (+ (= ABC*DEF TY 15) | * (+ (-* |ABC*DEFT/ 16) |G (+ (-* JABC*DEFT/G 17) IG ABC*DEFT/G * — at (+ * JABC*DEFT/G * — 19) | H (+ * JABC*DEFT/G *-H [20) | ) E [ABC*DEFT/G *—H* + nARARnRAAADpn pp ppp fp ppt STPAT LAAT AA AAO