introduction to data structures and types

A ppt on primitive and non primitive data structures, abstract data types , performance analysis(time and space complexity) using asymptotic notations-(Big O, Theta, Omega), introduction to arrays and their memory representation, types of arrays- single dimension, two dimension, multi-dimensions, basic operations on arrays- insertion, deletion, searching, sorting, sparse matrix and its representation, applications of array

1. Data Structures Unit-1 Introduction to Data Structures

2. Data Structures? Data :- Collection of raw facts Data structure :- representation of logical relation existing between individual elements of data Special format of storing and organizing data for better access and modification

3. Classification of Data Structure

4. Primitive DS Basic structures Directly operated upon by machine-level instructions Most common operations performed Create, select,update,delete

5. Non-Primitive DS More sophisticated data structures Derived from the primitive data structures Emphasize on structuring of a group of homogeneous and heterogeneous data items Linear Non Linear

6. Non-Primitive DS Linear Have homogeneous data elements Elements are in a sequence and form a linear pattern Easy to implement as memory of computer is also organized in linear fashion Eg :- stack , queue, linked list Non Linear A data item is connected to several other data items May exhibit a hierarchical relationship or parent –child relationship Not in a sequential structure Eg :- tree, graph Common operations:- traversal, search, sort, merge , insert,select,delete

7. Abstract Data Types

8. Abstract Data Types(ADT) ADT = collection of data + set of operations on that data ADT specifies What can be stored in ADT What operations can be done on ADT Abstraction? We know what a data type can do How it is done is hidden Definition of ADT :- ADT is defined as a mathematical model with a collection of operations defined on that model.

9. Abstract Data Types(ADT) Types of ADT Simple ADTs Predefined ( int , float , double,char,bool ) Consider integer ADT Has a predefined range Complex ADTs List , graph , queue,tree,stack

10. Abstract Data Types(ADT)

11. Performance Analysis

12. Fundamental Concepts Dynamic Memory allocation Recursion Performance analysis

13. Performance Analysis Problems and problem instances Eg :- Sorting in ascending order Problem: sorting Problem instance: eg -sorting data (2,4,1,7,5,0) Algorithms: quick,bubble,merge,selection,etc . Which is the best algo ? How to decide

14. Performance Analysis For judging algos , we check their complexity Definition:- It is the function which gives the running time or space in terms of input size Space Complexity Amount of memory needed to run to completion Time Complexity Amount of CPU time needed to run to completion

15. Space Complexity Space needed = fixed + variable Fixed Space Includes instructions,variables,constants Independent of number and size of I/O Variable space Includes dynamic allocation,function recursion Total space of any program S(P) = c + S p (instance) Constant or independent part eg :- int a,b,c ; Algo S( a,b,c ) { a=10; b =20; c= a+b ; } Variable part a= 1 time unit b = 1 time unit C = 1 time unit So, S(P) = 3 + 0 O(1) is the space complexity of this

16. Space Complexity S(P) = c + S p (instance) Variable part Eg :- let’s calculate sum of array a with n elements Algorithm Sum( a,n ) { total =0; for i =0 to n do total = total + a[ i ]; } So , S(P) = c + S p here , total , n and i are independent and so constant , so c =3. Now,calculating S p . Here a is dependent on n. Suppose n=5, then size of a = 5*n S(P) = 3 + 5*n ignoring constants , O(n) is the complexity

17. Time Complexity Best case If algo takes min time out of 10,20,30,40,50 (if task is to find 10) Worst case If algo takes max time Out of 10,20,30,40,50(if task is to find 50) Average case If algo takes avg time Out of 10,20,30,40,50(if task is to find 30)

18. Time Complexity 2 ways to calculate time complexity Frequency count or step count Asymptotic notations

19. Time Complexity using frequency count For comment and declaration #program to add two arrays Int a,b ; Step count = zero For return and assignment Int a=10; return b; Step count =1 Ignore lower order exponent when higher order exponent are present 3n 4 + n3 + 5n 2 + 23 = keep 3n 4 , ignore the rest Ignore constant multiplies 3n 4 ignore 3 from this Sum ( int a[], int n) { s=0; -------  1 for( i =0;i< n;i ++) --  n+1 (N TIMES CONDITION IS TRUE +1 FOR EXITING LOOP) s = s + a[ i ]; --- n return s; ----  1 } So time complexity is 1+n+1+n+1 = 3+2n = O(n)

20. Time complexity using asymptotic notations Big Oh notation(O) Big Omega notation( Ω ) Theta notation( Ө ) Little Oh notation(o) Little Omega notation(ᵚ)

21. Time complexity using asymptotic notation Big Oh notation(O) Mainly represents upper bound of algo’s running time Helps to find max time needed by an algo for execution(worst case) Let f(n),g(n) be two non-negative functions , then f(n)= O(g(n)) if there exists two positive constants C , n o such that f(n)<= C*g(n) , ɏ n>n

22. Time complexity using asymptotic notation Big Omega notation( Ω ) Mainly represents lower bound of algo’s running time Helps to find min time needed by an algo for execution(BEST case) Let f(n),g(n) be two non-negative functions , then f(n)= O(g(n)) if there exists two positive constants C , n o such that f(n)=> C*g(n) , ɏ n>n

23. Time complexity using asymptotic notation Theta notation( Ө ) Mainly represents average bound of algo’s running time Helps to find avg time needed by an algo for execution( avg case) Let f(n),g(n) be two non-negative functions , then f(n)= Ө (g(n)) if there exists three positive constants C 1 ,C 2 , n o such that C 1 *g(n)<= f(n)<= C 2 *g(n) , ɏ n>n

24. Time complexity using asymptotic notation Little Omega notation(ᵚ) Let f(n),g(n) be two non-negative functions , then f(n)= ᵚ(g(n)) such that lim [g(n)/f(n)] = 0 , n->infinity Little Oh notation(o) Let f(n),g(n) be two non-negative functions , then f(n)= o(g(n)) such that lim [f(n)/g(n)] = 0 , n->infinity

25. Time Complexity-general rules Rule 1:- Loops Its running time = running time of statements in it. Eg:for ( i =0;i< n;i ++) --  n+1 times it runs { s = s + i ;  n times } So time complexity = n + n+1 = 2n+1 = O(n) Rule 2:- Nested Loops Its running time = total running time of statements inside a group of loops is the product of sizes of all loops Eg :- for( i =0;i< n;i ++)---  n+1 { for(j=0; j< n;j ++)----  n*(n+1) c[ i ][j]=a[ i ][j]+b[ i ][j];--  n*n } So time complexity = n+n + n 2 +1 + n 2 = 2n 2 +2n + 1= O(n 2 ) Rule 3:- consecutive statements Its running time = maximum one Eg - for( i =0;i< n;i ++) ---  n+1 s= s + i ; - n for( i =0;i< n;i ++) --- n+1 { for (j=0;j< n;j ++) - - n*(n+1) { c[ i ][j]=a[ i ][j]+b[ i ][j]; ---  n*n } } So time complexity = 2n 2 +4n+2 = O(n 2 ) Rule 4:- if-else Its running time = max of if or else Eg :- if (n<=0) ---  1 return n; ----  1 else --- 1 { for( i =0;i< n;i ++) -----  n+1 s = s+ i ; -- n return s; -- 1 } so time complexity = 5 +2n = O(n)

26. Various Data Structures

27. Data Structures: Arrays Set of finite number of same data items One dimensional array An array with only one row or column Elements are stored in continuous locations Syntax is Datatype Array_name [size] int abc [6] 23 45 67 9 12 88 Maximum number of elements that can be stored in abc array 1 2 3 4 5 indexing Upper bound Lower bound 100 102 104 106 108 110 Base address Representation of linear array in memory

28. Data Structures: Arrays Length/size of an array is given by following equation ( Upperbound - lowerbound ) + 1 For int abc [6] , it would be (5-0) + 1 =6 Array can be written or read through a loop For( i =0;i<6;i++) { Scanf (“% d”,&abc [ i ]); Printf (“% d”,abc [ i ]); }

29. Array types Single dimensional array Array with one subscript Two dimensional array Array with two subscripts(row and column) Multi dimensional array Array with multiple subscripts

30. Basic operations of array Traversing Searching Insertion Deletion Sorting Merging

31. Traversing arrays Traversing:- used to access each element of array Start from beginning and go till end of array and access value of each element exactly once Eg :- int abc = {12,16,5,55,27} Algorithm : Traversal( abc,LB,UB ) abc is an array with lower bound LB and upper bound UB Step 1: for LOC= LB to UB do Step 2: Process abc [LOC] [End of for loop] Step 3: exit

32. Insertion into an array Insertion: add a new data item in the given collection of data items at a particular position Insertion at The beginning The end At a particular position Remember Array index starts from zero No. of elements = (UB-LB) + 1

33. Insertion into an array Insertion at end Algorithm Let A be an array of size N Step 1. If UB == N-1 Then print overflow and exit Step 2. Read data Step 3. UB = UB+1 Step 4. A[UB] =data Step 5. Exit 3 2 6 8 1 2 3 4 UB 12

34. Insertion into an array Insertion at beginning Algorithm Let A be an array of size N Step 1. If UB == N-1 Then print overflow and exit Step 2. Read data Step 3. K=UB Step 4. Repeat step 5 while K >= UB Step 5. A[K+1]= A[K] K = K-1 Step 6. A[LB] = data Step 7. Stop 3 2 6 8 1 2 3 4 UB 12 Start from here 12 3 2 6 8 A[4] = A[3] A[3]= A[2] A[2]= A[1] A[1]=A[0] A[0] = data

35. Insertion into an array Insertion at a location Algorithm Let A be an array of size N Step 1. If UB == N-1 Then print overflow and exit Step 2. Read data 12 Step 3. Read LOC (LOC = 2) Step 4. K=UB (k =3) Step 5. Repeat step 6 while K >= LOC (3>=2) Step 6. A[K+1] = A[K] K = K-1 Step 7. A[LOC] = data Step 8. Stop 3 2 6 8 1 2 3 4 UB 12 3 2 12 6 8 A[4] = A[3] K= 2 A[3] = A[2] K = 1 A[2]=12

36. Deletion from an array Deletion:- used to delete an existing data element from given collection of data items Delete from start Delete from end Delete from a particular position

37. Deletion from end of an array Deletion from end of array Algorithm Let A be an array of size N Step 1. If UB == NULL Then print underflow and exit Step 2. A[UB] = NULL Step 3. UB = UB-1 Step 4. Stop 3 2 6 8 1 2 3 4 UB 3 2 6 LB 1 2 UB

38. Deletion from start of an array Deletion from start of array Algorithm Let A be an array of size N Step 1. If UB == 0 Then print underflow and exit Step 2. K=LB Step 3. Repeat step 4, while K< UB Step 4. A[K] = A[K+1] K = K+1 Step 5. A[UB] = NULL UB = UB -1 Stop 3 2 6 8 1 2 3 4 UB 2 6 8 LB 1 2 UB Shifting

39. Deletion of a particular element of an array Deletion of a particular element Algorithm Let A be an array of size N Step 1. If UB == 0 Then print underflow and exit Step 2. Read DATA Step 3. K = LB Step 4. Repeat step 5 while A[K] = DATA Step 5. K = K+1 Step 6. Repeat step 7 while K < UB Step 7. A[K] = A[K+1] K = K + 1 Stop Step 8. A[UB] = NULL UB = UB -1 STOP 3 2 6 8 1 2 3 4 UB 3 2 8 LB 1 2 UB Shifting 9 9 3 Finding element to delete in array

40. Representation of an array in memory

41. Let’s find location (k) of an element For 1d array Loc(A[k]) = Base(A) + w*k w = words per memory cell Base(A) = starting address of array in memory

42. Consider an array A is declared as array of integers with size 50 and it’s first element is stored at memory address 101. So find out the address of 5 th element. Given (w = 4) Solution: - Given w = 4 , Base(A)=101 , k=5 Formula is Loc(A[k]) = Base(A) + w*k Loc(A[5]) = 101 + 4*5 = 121

43. Consider an array A, which records the number of t.v . sold each year from 1975 to 2000. Suppose that Base(A) = 101 and w = 4. Find out location of value of year 1990. Solution :- Given w =4 and B(A) =101 Formula is Loc(A[k]) = Base(A) + w*k Let’s find k 1990 -1975 = 15 = k Now Loc (A[15]) = 101 + 4*15 = 161

44. Two dimensional arrays

45. Two dimensional array Its arrangement of elements in rows and columns Has two indices 1 st represents rows 2 nd represents columns Eg :- int abc [4][4] Datatype name[no of rows][no of columns]

46. Two dimensional array

47. Initializing a 2d array

48. Initializing an unsized 2d array

49. Accessing 2d array elements

50. Inputting values in 2d array

51. Displaying values of 2d array

52. Matrix addition

53. Sparse Matrix

54. Sparse Matrix Matrix with more zeros than non zero elements

55. Representation of sparse matrix In 2 ways Arrays 2d array consisting of 3 rows Linked list Will be covered after linked list topic

56. Applications of array Used to store list value Used to perform matrix operations Used to implement searching algorithms Used to implement sorting algorithms Used to implement stack and queue Used to represent sparse matrix

57. GTU Questions Discuss various types of data structures with examples. [03] Compare array and linked list[03] Compare primitive and non primitive datatypes [04] Differentiate between data types and data structures[03] Answer the followings [04] A) Give examples of linear and non linear data structures B) What do you mean by abstract data types? What is time complexity? Explain with example.[03] Explain Asymptotic Notations in detail[07]