DATA STRUCTURES LECTURE NOTES Dr K VENKATA NAGENDRA Mr G RAJESH OBJECTIVES The course should enable the students to DATA STRUCTURES 18CS202 1 Demonstrate familiarity with major algorithms and data structures 2 Choose the appropriate data structure and algorithm design method for a specified application 3 Determine which algorithm or data structure to use in different scenarios 4 To improve the logical ability UNIT I INTRODUCTION TO ALGORITHMS AND DATA STRUCTURES Classes 12 Algorithms Definition Properties Performance Analysis Space Complexity Time Complexity Asymptotic Notations Data structures Introduction Data Structures types DS Operations UNIT II STACKS AND QUEUES Stacks Introduction Stack Operations Applications Infix to Postfix Conversion Evaluation of Postfix Expression ueues Introduction Operations on queues Circular queues Priority queues Classes 12 UNIT III LINKED LISTS AND APPLICATIONS Linked lists Introduction Singly linked lists Circular linked lists Doubly linked lists Multiply linked lists Applications Polynomial Representation Implementation of Stack and Queue using linked list Classes 12 UNIT IV SORTING AND SEARCHING Classes 12 Sorting Introduction Selection sort Bubble sort Insertion sort Merge sort Quick sort Heap Sort Searching Introduction Linear search Binary search Fibonacci search UNIT V TREES AND BINARY TREES Trees Introduction Definition and basic terminologies Representation of trees Binary Trees Basic Terminologies and Types Binary Tree Traversals Binary Search Trees Classes 12 Text Books 1 G A V PAI Data Structures and Algorithms Concepts Techniques and Applications Volume1 1stEdition Tata McGraw Hill 2008 2 Richard F Gilberg Behrouz A Forouzan Data Structures Pseudo code Approach with C 2ndEdition Cengage Learning India Edition 2007 Reference Books 1 Langsam M J Augenstein A M Tanenbaum Datastructures using C and C 2nd Edition PHI Education 2008 2 Sartaj Sahni Ellis Horowitz Fundamentals of at Structures in C 2nd Edition Orientblackswan 2010 Web References 1 https www geeksforgeeks org data structures 2 https www programiz com dsa 3 https www w3schools in data structures tutorial intro Outcomes At the end of the course students able to 1 Apply Concepts of Stacks Queues Linked Lists 2 Develop Programs for Searching and Sorting Trees 3 Interpret concepts of trees 4 Develop programs for Sorting and Searching UNIT I INTRODUCTION TO ALGORITHMS AND DATA STRUCTURES Definition An algorithm is a Step By Step process to solve a problem where each step indicates an intermediate task Algorithm contains finite number of steps that leads to the solution of the problem Properties Characteristics of an Algorithm Algorithm has the following basic properties Input Output Algorithm takes 0 or more input and produces the required output This is the basic characteristic of an algorithm Finiteness An algorithm must terminate in countable number of steps Definiteness Each step of an algorithm must be stated clearly and unambiguously Effectiveness Each and every step in an algorithm can be converted in to programming language statement Generality Algorithm is generalized one It works on all set of inputs and provides the required output In other words it is not restricted to a single input value Categories of Algorithm Based on the different types of steps in an Algorithm it can be divided into three categories namely Sequence Selection and Iteration Sequence The steps described in an algorithm are performed successively one by one without skipping any step The sequence of steps defined in an algorithm should be simple and easy to understand Each instruction of such an algorithm is executed because no selection procedure or conditional branching exists in a sequence algorithm Example adding two numbers Step 1 start Step 2 read a b Step 3 Sum a b Step 4 write Sum Step 5 stop Selection The sequence type of algorithms are not sufficient to solve the problems which involves decision and conditions In order to solve the problem which involve decision making or option selection we go for Selection type of algorithm The general format of Selection type of statement is as shown below if condition Statement 1 else Statement 2 The above syntax specifies that if the condition is true statement 1 will be executed otherwise statement 2 will be executed In case the operation is unsuccessful Then sequence of algorithm should be changed corrected in such a way that the system will re execute until the operation is successful 1 n n 10 b s s r c Iteration Iteration type algorithms are used in solving the problems which involves repetition of statement In this type of algorithms a particular number of statements are repeated n no of times Example1 Step 1 start Step 2 read n Step 3 repeat step 4 until n 0 Step 4 a r n mod 10 Step 5 write s Step 6 stop Performance Analysis an Algorithm The Efficiency of an Algorithm can be measured by the following metrics i Time Complexity and ii Space Complexity i Time Complexity The amount of time required for an algorithm to complete its execution is its time complexity An algorithm is said to be efficient if it takes the minimum reasonable amount of time to complete its execution ii Space Complexity The amount of space occupied by an algorithm is known as Space Complexity An algorithm is said to be efficient if it occupies less space and required the minimum amount of time to complete its execution 1 Write an algorithm for roots of a Quadratic Equation Roots of a quadratic Equation Step 1 start Step 2 read a b c Step 3 if a 0 then step 4 else step 5 Step 4 Write Given equation is a linear equation Step 5 d b b 4 a c Step 6 if d 0 then step 7 else step8 Step 7 Write Roots are real and Distinct Step 8 if d 0 then step 9 else step 10 Step 9 Write Roots are real and equal Step 10 Write Roots are Imaginary Step 11 stop 2 2 Write an algorithm to find the largest among three different numbers entered by user Step 1 Start Step 2 Declare variables a b and c Step 3 Read variables a b and c Step 4 If a b If a c Display a is the largest number Else Display c is the largest number Else If b c Display b is the largest number Else Display c is the greatest number Step 5 Stop 3 Write an algorithm to find the factorial of a number entered by user Step 1 Start Step 2 Declare variables n factorial and i Step 3 Initialize variables factorial 1 i 1 Step 4 Read value of n Step 5 Repeat the steps until i n 5 1 factorial factorial i 5 2 i i 1 Step 6 Display factorial Step 7