Unit_I_Complete.pdf

Data Structures (CSE2PM01A)(PM) S. Y. B. Tech CSE Semester – III DEPARTMENT OF COMPUTER ENGINEERING & TECHNOLOGY  Data Structures (CSE2PM01A) ⮚ Pre-requisites ⮚ Programming Foundations ⮚ Course Objectives ⮚ Knowledge ⮚ Learn the data structure and its fun...

Data Structures (CSE2PM01A)(PM) S. Y. B. Tech CSE Semester – III DEPARTMENT OF COMPUTER ENGINEERING & TECHNOLOGY  Data Structures (CSE2PM01A) ⮚ Pre-requisites ⮚ Programming Foundations ⮚ Course Objectives ⮚ Knowledge ⮚ Learn the data structure and its fundamental concept. ⮚ Skills ⮚ Understand the different Linear and nonlinear data structures such as Arrays, Stacks, Queues Trees and Graph. ⮚Study the different Sorting Techniques and concepts of Heap and Trees ⮚ Attitude ⮚Learn how to apply Data Structures to solve Real-life Problems 2  Data Structures (CSE2PM01A) ⮚ Course Outcomes ⮚ After completion of this course students will be able to: ⮚ To demonstrate the use of sequential data structures ⮚ To analyse different sorting algorithms so as to understand their applications ⮚ To develop skills for writing and analysing algorithms to solve domain problems ⮚ To choose appropriate non-linear data structures to solve a given problem 3  Data Structures (CSE2PM01A) ⮚ Unit 1 – Introduction to Data Structures: Data, Data Objects, Abstract Data types (ADT) and Data Structures, Types of data structures (Linear and Non-linear, Static and dynamic) Introduction to algorithms Analysis of Algorithms- Space complexity, Time complexity, Asymptotic notations-Big-O, Theta and Omega, Sorting: Types of Sorting-Internal and External Sorting, General Sort Concepts- Sort Order, Stability, Efficiency, and Number of Passes, Comparison Based Sorting Methods-Bubble Sort, Insertion Sort, Selection Sort, Shell Sort, Comparison of all sorting algorithm ⮚ UNIT 2 – Linear Data Structures: Arrays, Array as an Abstract Data Type, Sequential Organization, Storage Representation and their Address Calculation: Row major and Column Major, Multidimensional Arrays: Concept of Ordered List, Single Variable Polynomial: Representation using arrays, Polynomial as array of structure, Polynomial addition, Polynomial evaluation and Polynomial multiplication. Sparse Matrix: Sparse matrix representation using array, Sparse matrix addition, Transpose of sparse matrix- Simple and Fast Transpose, Time and Space trade-off. 4  Data Structures (CSE2PM01A) ⮚ UNIT – 3: Stacks and Queues: Stacks: Stack as an Abstract Data Type, Representation of Stack Using Sequential Organization, stack operations, Applications of Stack- Expression Conversion and Evaluation, Linked Stack and Operations, Recursion. Queues: Queue as Abstract Data Type, Representation of Queue Using Sequential Organization, Queue Operations Circular Queue, Advantages of Circular queues, Linked Queue and Operations Deque-Basic concept, types (Input restricted and Output restricted), Application of Queue: Job scheduling. 5  Data Structures (CSE2PM01A) ⮚ UNIT – 4: Linked List: Linked List as an Abstract Data Type, Representation of Linked List Using Sequential Organization, Representation of Linked List Using Dynamic Organization, Types of Linked List: singly linked, Circular Linked Lists,Doubly Linked List, Primitive Operations on Linked List, Polynomial Manipulations-Polynomial addition. Generalized Linked List (GLL) concept, Representation of Polynomial using GLL. Case Study: Garbage Collection ⮚ Unit – 5 Basic Terminology, Binary Tree- Properties, Converting Tree to Binary Tree, Representation using Sequential and Linked organization, Binary tree creation and Traversals, Binary Search Tree (BST) and its operations, threaded binary tree- Creation and Traversal of In-order Threaded Binary tree. Heap- Heap as a priority queue, Heap sort. 6  Data Structures Lab 1. Write a program to create a student database using an array of structures. Apply sorting techniques (Bubble sort , Insertion Sort, Selection Sort). 2. Write a C program for sparse matrix realization and operations on it- Simple Transpose, Fast Transpose. 3. Implement stack as an ADT and apply it for different expression conversions (infix to postfix or infix to prefix (Any one), prefix to postfix or prefix to infix, postfix to infix or postfix to prefix (Any one)). 4. Queues are frequently used in computer programming, and a typical example is the creation of a job queue by an operating system. If the operating system does not use priorities, then the jobs are processed in the order they enter the system. Write a program for simulating job queue. Write functions to add job and delete job from queue. 5. Department of Computer Engineering has student's club named 'Pinnacle Club'. Students of second, third and final year of department can be granted membership on request. Similarly, one may cancel the membership of club. First node is reserved for president of club and last node is reserved for the secretary of the club. Write C program to maintain club member ‘s information using singly linked list. Store student PRN and Name. Write functions to: a) Add and delete the members as well as president or even secretary. b) Compute total number of members of club c) Display members d) sorting of two linked list e) merging of two linked list f) Reversing using three pointers. 7  Data Structures Lab List of Lab Assignments 6. Implement binary tree and perform following operations: Creation of binary tree and traversal recursive and non-recursive. 7. Implement a dictionary using a binary search tree where the dictionary stores keywords & its meanings. Perform following operations: Insert a keyword, Delete a keyword, Create mirror image and display level wise, Copy 8. Implement a threaded binary tree. Perform inorder traversal on the threaded binary tree. 9. Read the marks obtained by students of second year in an online examination of a particular subject. Find the maximum and minimum marks obtained in that subject. Use heap data structure and heap sort. 8 Data Structures (CSE2PM01A) Evaluation Components-Theory(CCA) DS Theory Components Components Planned Units Planned Dates Tentative Marks CCA-1 ( Quiz and 1 ,2,3 10-Aug-24 15 Problem Solving ) CCA- 2 ( Active 4 ,5 23-Oct-24 15 Learning ) Mid Term Exam 1,2,3 7-Oct-24 30 End Term Exam 1,2,3,4, 5 25-Nov 40 Unit wise Weight Unit 1 Unit 2 Unit 3 Unit 4 Unit 5 20 M 20 M 20 M 20 M 20 M  Evaluation Components- DS Lab Components Planned Planned Dates Tentative Marks Assignments (Tentative) LCA 1 1,2,4 14-Aug-24 30 LCA 2 3,5,6,7 20-Sep-24 35 LCA 3 8, 9 + Practical 17-Nov-24 35 Exam  Data Structures (CSE2PM01A) ⮚ Learning Resources: ⮚ Text Books: 1. Fundamentals of Data Structures, E. Horowitz, S. Sahni, S. A-Freed, Universities Press. 2. Data Structures and Algorithms, A. V. Aho, J. E. Hopcroft, J. D. UIlman, Pearson. ⮚ Reference Books: 1. The Art of Computer Programming: Volume 1: Fundamental Algorithms, Donald E. Knuth. 2. Introduction to Algorithms, Thomas, H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, The MIT Press. 3. Open Data Structures: An Introduction (Open Paths to Enriched Learning), (Thirty First Edition), Pat Morin, UBC Press. 11  Data Structures (CSE2PM01A) ⮚ Supplementary Readings: 1. Aaron Tanenbaum, “Data Structures using C”, Pearson Education. 2. R. Gilberg, B. Forouzan, "Data Structures: A pseudo code approach with C", Cenage Learning, ISBN 9788131503140. ⮚ Web Resources: ⮚ Web Links: ⮚ https://www.tutorialspoint.com/data_structures_algorithms/ ⮚ MOOCs: ⮚ http://nptel.ac.in/courses/106102064/1 ⮚ https://nptel.ac.in/courses/106103069/ 12  Introduction to Data Structures ❑ Data, Data objects, Data Types ❑ Abstract Data types (ADT) and Data Structure ❑ Types of data structure ❑ Introduction to Algorithms ❑ Algorithm Design Tools: Pseudo code and flowchart ❑ Analysis of Algorithms- Space complexity, Time complexity, Asymptotic notations - Big-O, Theta and Omega, ❑ Types of Sorting-Internal and External Sorting, 13 Introduction to Data Structures General Sort Concepts-Sort Order, Stability, Efficiency, and Number of Passes, Comparison Based Sorting Methods-Bubble Sort Insertion Sort, Selection Sort, Shell Sort Comparison of all sorting algorithm 14  Data, Data Objects and Data Types ⮚ Computer Science is study of data ⮚ Machines that hold data ⮚ Languages for describing data manipulations ⮚ Foundations which describe what kinds of refined data can be produced from raw data (actual sensor data, Google form data) ⮚ Structures of refining data (sensor data w/o outliers) 15  Data, Data Objects and Data Types Data is of two types ❑ Atomic Data It consist of single piece of information. It cannot be divided into other meaningful pieces of data. e.g Name of Person, Name of Book ❑Composite Data It can be divided into subfields that have meaning. e.g. Address, Telephone number 16  Data, Data Objects and Data Types Data Objects Roll_ Number Data object is referring to set of elements say D. For Example: Data Object integers refers to Name D={0,±1,±2,…………………} Percentage Data Object represents an object having a data. For Example: If student is one object then it will consist of different data like roll no, name, percentage, address etc. 17  Data, Data Objects and Data Types ⮚ Data Types ⮚ A Data type is a term which refers to the kinds of data that variables may hold in a programming languages. ⮚ For Example: In C programming languages, the data types are integer, float, character etc. ⮚ Data type is a way to classify various types of data such as integer, string, etc. which determines the values that can be used with the corresponding type of data, the type of operations that can be performed on the corresponding type of data. ⮚ There are two data types − ⮚ Built-in Data Type ⮚ Derived Data Type 18  Data, Data Objects and Data Types Built-in Data Type Derived Data Type Those data types for which a language These data types are normally built by the has built-in support are known as Built-in combination of primary or built-in data Data types. types and associated operations on them. For example, most of the languages provide the following built-in data For example − types. o List (dynamic arrays) ◦ Integers o Array o Structure ◦ Boolean (True, False) o Pointers in C ◦ Floating (Decimal numbers) ◦ Character and Strings 19  Abstract Data Type(ADT) and Data Structure ❑Abstract Data Type Abstract Data Type consist of ❑ Concern about what can be done ❑Declaration of Data not how it can be done ❑Declaration of Operations ❑Encapsulation of data and operations 20  Abstract data types An abstract data type is a type with associated operations, but whose representation is hidden. The calculator explains it very well. One can use it different ways by giving various values and perform operations. But, mechanism how the operation is done is not shown. This process of hiding the information is called as Abstraction. 21  Abstract Data Types (ADT) ▪ An ADT is composed of ▪ A collection of data ▪ A set of operations on that data ▪ Specifications of an ADT indicate ▪ What the ADT operations do, not how to implement them ▪ Implementation of an ADT ▪ Includes choosing a particular data structure 22  Abstract Data Type(ADT) and Data Structure Abstract Data Type Examples structure ARRAY(value, index) declare CREATE()→array RETRIVE(array,index)→value ❑ Array STORE(array,index,value)→array; ❑ Tree for all A ε array, i,j ε index ,x ε value let RETRIVE (CREATE,i) : : = error ❑ Graph RETRIVE (STORE(A,i,x),j) : : = ❑ Linked List if EQUAL(i,j) then x else RETRIVE(A,j) ❑ Matrix end end ARRAY 23  Data Structure ⮚ A data structure is a set of domains D, a structured domain d ε D, a set of functions F and a set of axioms A. ⮚The triple(D,F,A) denotes the data structure d ε D and it will usually be abbreviated by writing d. ⮚ The triple(D,F,A) is referred to as an abstract data type (ADT). ⮚ It is called abstract precisely because the axioms do not imply a form of representations/implementation. 24  Data Structure Example Structure NATNO D=NATNO Declare ZERO() → natno D ε D= {Boolean, natno} ISZERO(NATNO) → Boolean F={ZERO,ISZERO,ADD,SUCC} SUCC(natno) → natno ADD(natno,natno) → natno for all x,y ε natno let AXIOMS ISZERO(ZERO) :: = true; ADD(ZERO,y) :: =y; ISZERO(SUCC(x))= false 25  Types of Data Structures ⮚ Linear data structure: ⮚ The data structure where data items are organized sequentially or linearly where data elements attached one after another is called linear data structure. It has unique predecessor and Successor. ⮚ Ex: Arrays, Linked Lists ⮚ Non-Linear data structure: ⮚ The data structure where data items are not organized sequentially is called non linear data structure. It don’t have unique predecessor or Successor. ⮚ In other words, A data elements of the non linear data structure could be connected to more than one elements to reflect a special relationship among them. ⮚ Ex: Trees, Graphs 26  Types of Data Structures Linear Data Structure Non Linear Data Structure 27  Types of Data Structures ⮚ Static data structure: ⮚ Static Data structure has fixed memory size. It is the memory size allocated to data, which is static. ⮚ Ex: Arrays ⮚ Dynamic data structure: ⮚ In Dynamic Data Structure, the size can be randomly updated during run time which may be considered efficient with respect to memory complexity of the code. ⮚ Ex: Linked List ⮚In comparison to dynamic data structures, static data structures provide easier access to elements. Dynamic data structures, as opposed to static data structures, are flexible. 28  Introduction to Algorithms Algorithm ⮚ Solution to a problem that is independent of any programming language. ⮚ Sequence of steps required to solve the problem ⮚ Algorithm is a finite set of instructions that if followed, accomplishes a particular task ⮚ All algorithms must satisfy the following criteria: ⮚ Input: Zero or more Quantities are externally supplied ⮚ Output: At least one quantity is produced ⮚ Definiteness: Each instruction is clear and unambiguous ⮚ Finiteness: if we trace out the instructions of an algorithm then for all cases the algorithm terminates after a finite number of steps. ⮚ Effectiveness: Every instruction must be very basic so that it can be carried out in principle by a person using pencil and paper. 29  Introduction to Algorithms Program vs Algorithm ⮚ A program is a written out set of statements in a language that can be executed by the machine. ⮚ An algorithm is simply an idea or a solution to a problem that is often procedurally written. 30  Introduction to Algorithms Example : Finding the largest integer among five integers 31  Introduction to Algorithms Defining actions in Find Largest algorithm 32  Introduction to Algorithms Find Largest refined 33 Introduction to Algorithms 34 Introduction to Algorithms Three constructs 35  Algorithm Design Tools Pseudo Code ❑is an artificial and informal language that helps programmers develop algorithms. ❑Uses English-like phrases with some Visual Basic terms to outline the program Flowchart ❑Graphical representation of an algorithm. ❑Graphically depicts the logical steps to carry out a task and shows how the steps relate to each other. 36  Algorithm Design Tools Flowchart Example 1: Print 1 to 20: Algorithm Step 1: Initialize X as 0, Step 2: Increment X by 1, Step 3: Print X, Step 4: If X is less than 20 then go back to step 2. 37  Pseudo Code Algorithm SORT(A, n) ❑Pseudocode is an informal high-level description { of the operating principle of a computer program or for (i =1;ia 0 1 2 3 4 5 6 7 8 9 swap 33 22 44 88 11 99 77 55 66 01 a>a swap 0 1 2 3 4 5 6 7 8 9 33 22 44 66 11 99 77 55 88 01 0 1 2 3 4 5 6 7 8 9 33 22 44 66 01 99 77 55 88 11  0 1 2 3 4 5 6 7 8 9 01 11 22 33 44 55 77 66 88 99 0 1 2 3 4 5 6 7 8 9 01 11 22 33 44 55 66 77 88 99 0 1 2 3 4 5 6 7 8 9 01 11 22 33 44 55 66 77 88 99  Shell sort- Complexity Analysis 1. Complexity in the Best Case: O(n*Log n) The total number of comparisons for each interval (or increment) is equal to the size of the array when it is already sorted. 1. Complexity in the Average Case: O(n*log n) It's somewhere around O. (n1.5) 1. Complexity in the Worst-Case Scenario: Less Than or Equal to O (n2) Shell sort's worst-case complexity is always less than or equal to O. (n2) The degree of complexity is determined by the interval picked. The above complexity varies depending on the increment sequences used. The best increment sequence has yet to be discovered. 7/4/2024 Data Structures UNIT-I 108 Non-comparison sorting algorithm The sorting algorithms that sort the data without comparing the elements are called non-comparison sorting algorithms. The examples for non-comparison sorting algorithms are counting sort, bucket sort, radix sort, and others. 7/4/2024 Data Structures UNIT-I 109  COMPARISON OF ALL SORTING METHODS sort Best Average Worst stable In place Comparison based sorting Bubble ✓ ✓ ✓ Ω(N2) Θ(N2) O(N2) Insertion ✓ ✓ ✓ Ω(N) Θ(N2) O(N2) Selection X ✓ ✓ Ω(N2) Θ(N2) O(N2) Shell Ω(n log(n)) O(n*log n) O(N2) X ✓ ✓ Radix X X X Ω(N k) Θ(N k) O(N k) Bucket ✓ X X Ω(N + k) Θ(N + k) O(N2) Merge ✓ X ✓ Ω(N log N) Θ(N log N) O(N log N) Quick X ✓ ✓ Ω(N log N) Θ(N log N) O(N2) 7/4/2024 Data Structures UNIT-I 110 COMPARISON OF ALL SORTING METHODS Practice Problem Statement 1.Given a sorted array Arr[](0-index based) consisting of N distinct integers and an integer k, the task is to find the index of k, if it’s present in the array Arr[]. Otherwise, find the index where k must be inserted to keep the array sorted. 2.There are n tree in a forest. Heights of the trees is stored in array tree[ ]. If ith tree is cut at height h, the wood obtained is tree[i]-h, given that tree[i]>h. If total wood needed is k (not less, neither more) find the height at which every tree should be cut (all trees have to be cut at the same height). 3.Given an integer K and an array height[] where height[i] denotes the height of the ith tree in a forest.The task is to make a cut of height X from the ground such that exactly K unit wood is collected.If it is not possible then print -1 else print X. 7/4/2024 Data Structures UNIT-I 115 Practice Problem Statement 4. Given a sorted array with possibly duplicate elements, the task is to find indexes of first and last occurrences of an element x in the given array. 5.Given an array of integers. Find a peak element in it. An array element is a peak if it is NOT smaller than its neighbours. For corner elements, we need to consider only one neighbour. 6.Given a sorted and rotated array A of N distinct elements which is rotated at some point, and given an element K.The task is to find the index of the given element K in the array A. 7/4/2024 Data Structures UNIT-I 116 Practice Problem Statement 7.Given two arrays A and B contains integers of size N and M, the task is to find numbers which are present in the first array, but not present in the second array. 8.Given an integer x, find the square root of x. If x is not a perfect square, then return floor(√x). 7/4/2024 Data Structures UNIT-I 117 Practice Problem Statement Given an array of distinct integers. Sort the array into a wave-like array and return it. In other words, arrange the elements into a sequence such that a1 >= a2 = a4