DDS_Unit_1.pdf

UNIT 1 Introduction Prof. Keval Mehta, Sr. Cyber Security Trainer Computer Science & Engineering  Topic-1 Introduction Introduction “Data Structures and Algorithms” is one of the classic, core topics of Computer Science. Data structures and algorithms ar...

UNIT 1 Introduction Prof. Keval Mehta, Sr. Cyber Security Trainer Computer Science & Engineering  Topic-1 Introduction Introduction “Data Structures and Algorithms” is one of the classic, core topics of Computer Science. Data structures and algorithms are central to the development of good quality computer programs. Program= algorithm + Data Structure Image source : Google Introduction What is Algorithms? In mathematics and computer science, an algorithm is a set of instructions, typically to solve a class of problems or perform a computation. Algorithm is a step by step procedure to solve a particular function. Introduction It is important for every Computer Science student to understand the concept of Information and how it is organized or how it can be utilized. What is Information? If we arrange some data in an appropriate sequence, then it forms a Structure and gives us a meaning. This meaning is called Information Two things in Information: One is Data and the other is Structure. Introduction What is Data? Facts and statistics collected together for reference or analysis. What is Data Structure? A data structure is a systematic way of organizing and accessing data. A data structure tries to structure data! – Usually more than one piece of data – Should define legal operations on the data – The data might be grouped together Introduction Data Structures are the main part of many computer science algorithms as they enable the programmers to handle the data in an efficient way. It plays an important role in enhancing the performance of a software or a program as the main function of the software is to store and retrieve the user's data as fast as possible. That means, algorithm is a set of instruction written to carry out certain tasks & the data structure is the way of organizing the data with their logical relationship retained. To develop a program of an algorithm, we should select an appropriate data structure for that algorithm. Therefore algorithm and its associated data structures form a program.  Topic-2 Classification of Data Structure Classification of Data Structure Image source : Google Classification of Data Structure Data Structures are normally classified into two broad categories 1. Primitive Data Structure 2. Non-primitive data Structure Primitive Data Structure Primitive data structures are basic structures and are directly operated upon by machine instructions. It have different representations on different computers. Integer: allows all values without fraction part. Float: used for storing fractional numbers. Character: used for character values. Pointer: holds memory address of another variable Non Primitive Data Structure These are derived from primitive data structures. The non-primitive data structures emphasize on structuring of a group of homogeneous or heterogeneous data items. Examples of Non-primitive data type are Array, List, and File etc. A Non-primitive data type is further divided into Linear and Non-Linear data structure  Non Primitive Data Structure Array: An array is a fixed-size sequenced collection of elements of the same data type. List: An ordered set containing variable number of elements is called as Lists. File: A file is a collection of logically related information. It can be viewed as a large list of records consisting of various fields. Image source : Google Non Primitive Data Structure : Linear data structures Data is arranged in such a way that after one element we have just one more element that is, a single element is connected to just one more element after it. Examples of Linear Data Structure are Stack and Queue, linked list. Image source : Google Non Primitive Data Structure : Linear data structures Stack: Stack is ordered linear data structure which is modified form of an array. a data structure in which insertion and deletion operations are performed at one end only. Stack is also called as Last in First out (LIFO) data structure. Queue: The data structure which permits the insertion at one end and Deletion at another end, known as Queue. Queue is also called as First in First out (FIFO) data structure. Non Primitive Data Structure : Linear data structures If after one element, we have connection to multiple elements then such data structures are called as non linear data structures. Examples of Non-linear Data Structure are Tree and Graph. Image source : Google Non Primitive Data Structure : Linear data structures Tree: A tree can be defined as finite set of data items (nodes) in which data items are arranged in branches and sub branches according to requirement. Trees represent the hierarchical relationship between various elements. Tree consist of nodes connected by edge, the node represented by circle and edge lives connecting to circle. Non Primitive Data Structure : Linear data structures Graph: Graph is a collection of nodes (Information) and connecting edges (Logical relation) between nodes. A tree can be viewed as restricted graph. Graphs have many types: Un-directed Graph Multi Graph Simple Graph Directed Graph Mixed Graph Null Graph Weighted Graph Difference between Linear and Non Linear Data Structure Linear Data Structure Non-Linear Data Structure Every item is related to its Every item is attached with many previous and next time. other items. Data is arranged in Data is not arranged in sequence. linear sequence. Data items can be traversed in Data cannot be traversed in a single run. a single run. Eg. Array, Stacks, linked list, Eg. tree, graph. queue. Implementation is easy. Implementation is difficult.  Topic-3 Operation on Data structure Operation on Data structure Operation means processing the data in the data structure. The following are some important operations Create – The create operation results in reserving memory for program elements. Destroy – Destroy operation destroys memory space allocated for specified data structure Selection – Selection operation deals with accessing a particular data within a data structure Operation on Data structure Traversing – Traversal is a process of visiting each and every node of a list in systematic manner Updation – It updates or modifies the data in the data structure. Searching – To search for a particular value in the data structure for the given key value. Sorting – To arrange the values in the data structure in a particular order. Operation on Data structure Inserting – To add a new value to the data structure Deleting – To remove a value from the data structure Splitting – Splitting is a process of partitioning single list to multiple list. Merging – To join two same type of data structure values  Topic-4 Review of an Array Review of an Array Overview of Arrays in C An array is a collection of variables of the same type that are stored in contiguous memory locations. Arrays allow you to store multiple items of the same type together, which can be accessed using an index. Declaration and Initialization Declaration: You declare an array by specifying the type of its elements and the number of elements required by an array as follows: datatype arrayName[arraySize]; int numbers; // an array of 5 integers Review of an Array Initialization: Arrays can be initialized at the time of declaration. For example: int numbers = {1, 2, 3, 4, 5}; // an array of 5 integers with values If you don't specify all elements, the remaining will be initialized to 0. int numbers = {1, 2}; // {1, 2, 0, 0, 0} Accessing Elements Array elements are accessed using their index. Indexing starts from 0, so the first element is arrayName. int first = numbers; // Access the first element numbers = 10; // Set the third element to 10  Review of an Array Iterating Through an Array You can use loops to iterate through the elements of an array. A for loop is commonly used for this purpose. for(int i = 0; i < 5; i++) { printf("%d ", numbers[i]); } Multi-dimensional Arrays C supports multi-dimensional arrays. For example, a two-dimensional array (a matrix) can be declared and initialized as follows: int matrix = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} }; Review of an Array Key Points Memory Allocation: Arrays have a fixed size, which is determined at compile-time. The size of an array cannot be altered at runtime. Contiguous Memory: Array elements are stored in contiguous memory locations, which allows for efficient indexing and iteration. Bounds Checking: C does not perform bounds checking. Accessing elements outside the array's range can result in undefined behavior. Pointers and Arrays: In many contexts, the name of an array is treated as a pointer to its first element. For example, numbers is equivalent to &numbers.  Topic-5 Structures, Self – Referential Structures, and Unions  Structure The structure in C is a user-defined data type that can be used to group items of possibly different types into a single type. The struct keyword is used to define the structure in the C programming language. The items in the structure are called its member and they can be of any valid data type. Syntax struct structure_name { data_type member_name1; data_type member_name1;........ };  Structure #include struct str1 { int i; char c; float f; char s; }; void main() { struct str1 var1 = { 1, 'A', 1.00, "GeeksforGeeks" }; printf("Struct 1:\n\ti = %d, c = %c, f = %f, s = %s\n",var1.i, var1.c, var1.f, var1.s); return 0; } Self – Referential Structure Self Referential structures are those structures that have one or more pointers which point to the same type of structure, as their member. Self – Referential Structure struct node { int data1; char data2; struct node* link; }; int main() { struct node ob; return 0; } Union The Union is a user-defined data type in C language that can contain elements of the different data types just like structure. But unlike structures, all the members in the C union are stored in the same memory location. Due to this, only one member can store data at the given instance. Syntax of Union in C union union_name { datatype member1; datatype member2; }; Union Different Ways to Define a Union Variable 1. With Union Declaration 2. After Union Declaration Defining Union Variable with Defining Union Variable after Declaration Declaration union union_name { union union_name var1, datatype member1; var2, var3...; datatype member2;... } var1, var2,...; Union #include // union template or declaration // driver code union un { void main() { int member1; union un var1; char member2; var1.member1 = 15; float member3; printf("The value stored in member1 = %d", var1.member1); }; } Pointers and Dynamic Memory Allocation Functions Pointer: A pointer is a variable that stores the memory address of another variable. Declaration and Initialization: int *ptr; // Declare a pointer to an integer int var = 10; ptr = &var; // Initialize the pointer with the address of var Dereferencing: Access the value stored at the pointer's address using the * operator. int value = *ptr; // value is now 10 Pointers and Dynamic Memory Allocation Functions Key Points: Null Pointer: Initialized to NULL to avoid undefined behavior. Pointer to Pointer: Stores the address of another pointer. int **pptr = &ptr; // Pointer to a pointer Use Cases: Efficient array manipulation, dynamic memory, complex data structures. Simple Example of Pointer #include int main() { printf("Pointer Basics\n"); int a =76; int *ptra=&a int *ptr2= NULL; printf("The Address of pointer is %p\n", &ptra ); printf("The Address of a is %p\n," &a); printf("The Address of a is %p\n",ptra ); printf("The Address of some garbage is %p\n",ptr2); printf("The Value of a is %d\n", *ptra ); printf("The Value of a is %d\n", *a ); return 0; } Pointers and Dynamic Memory Allocation Functions Key Points: Null Pointer: Initialized to NULL to avoid undefined behavior. Pointer to Pointer: Stores the address of another pointer. int **pptr = &ptr; // Pointer to a pointer Use Cases: Efficient array manipulation, dynamic memory, complex data structures.  Dynamic Memory Allocation Functions C malloc() method The “malloc” or “memory allocation” method in C is used to dynamically allocate a single large block of memory with the specified size. It returns a pointer of type void which can be cast into a pointer of any form. It doesn’t Initialize memory at execution time so that it has initialized each block with the default garbage value initially. Syntax of malloc() in C : ptr = (cast-type*) malloc(byte-size) For Example: ptr = (int*) malloc(100 * sizeof(int)); Since the size of int is 4 bytes, this statement will allocate 400 bytes of memory. And, the pointer ptr holds the address of the first byte in the allocated memory. Dynamic Memory Allocation Functions  Dynamic Memory Allocation Functions C calloc() method 1. “calloc” or “contiguous allocation” method in C is used to dynamically allocate the specified number of blocks of memory of the specified type. it is very much similar to malloc() but has two different points and these are: 2. It initializes each block with a default value ‘0’. 3. It has two parameters or arguments as compare to malloc(). Syntax of calloc() in C: ptr = (cast-type*)calloc(n, element-size); For Example: ptr = (float*) calloc(25, sizeof(float)); This statement allocates contiguous space in memory for 25 elements each with the size of the float.  Dynamic Memory Allocation Functions C free() method “free” method in C is used to dynamically de-allocate the memory. The memory allocated using functions malloc() and calloc() is not de-allocated on their own. Hence the free() method is used, whenever the dynamic memory allocation takes place. It helps to reduce wastage of memory by freeing it. Syntax of free() in C: free(ptr); Dynamic Memory Allocation Functions C realloc() method “realloc” or “re-allocation” method in C is used to dynamically change the memory allocation of a previously allocated memory. In other words, if the memory previously allocated with the help of malloc or calloc is insufficient, realloc can be used to dynamically re-allocate memory. re-allocation of memory maintains the already present value and new blocks will be initialized with the default garbage value. Syntax of realloc() in C ptr = realloc(ptr, newSize); where ptr is reallocated with new size 'newSize'. Dynamic Memory Allocation Functions  //Use of realloc printf("Enter the size of t create\n"); //Use of calloc scanf("%d", &n); int *ptr; int n; ptr = (int *)realloc(ptr , printf("Enter the size of the array you want to create\n"); for (int i = 0; i < n; i++) scanf("%d", &n); { the array you want to printf("Enter the new v ptr = (int *)calloc(n , sizeof(int)); scanf("%d", &ptr[i]); for (int i = 0; i < n; i++) } { zeof(int)); printf("Enter the value no %d of this array\n",i); for (int i = 0; i < n; i++) scanf("%d", &ptr[i]); { } printf("The new value no %d of this ptr[i]); for (int i = 0; i < n; i++) } { printf("The value at %d of this array is %d\n",i, ptr[i]); free(ptr); } return 0;  Topic – 6 Representation of Linear Arrays in Memory, dynamically allocated arrays Representation of Linear Arrays in Memory, dynamically allocated arrays This procedure is referred to as Dynamic Memory Allocation in C. Therefore, C Dynamic Memory Allocation can be defined as a procedure in which the size of a data structure (like Array) is changed during the runtime. C provides some functions to achieve these tasks. There are 4 library functions provided by C defined under header file to facilitate dynamic memory allocation in C programming. They are: 1. malloc() 2. calloc() 3. free() 4. realloc()  Representation of Linear Arrays in Memory Contiguous Allocation: Elements are stored in consecutive memory locations. Address Calculation: Address of arr[i]=Base address+i×sizeof(type) Example: For int arr = {10, 20, 30, 40, 50} with a base address 0x1000: Key Points Efficient Access: Direct via indices. Fixed Size: Set at compile time. Memory Efficiency: Contiguous storage for fast access.  Representation of Linear Arrays in Memory Example For int arr = {10, 20, 30, 40, 50} with a base address 0x1000: Index Address Value arr 0x1000 10 arr 0x1004 20 arr 0x1008 30 arr 0x100C 40 arr 0x1010 50 Accessing Elements By index: int value = arr; // 30 By pointer: int value = *(arr + 2); // 30  Representation of Linear Arrays in Memory Dynamically allocated arrays: Allow flexible array sizes at runtime using pointers and memory functions. Key Functions 1. malloc: Allocates memory. int *arr = (int*)malloc(n * sizeof(int)); 2. free: Frees allocated memory. free(arr); Key Points Dynamic Size: Set at runtime. Efficient Use: Allocate and free as needed.  Representation of Linear Arrays in Memory Example: for (int i = 0; i < n; i++) { #include arr[i] = i + 1; #include } int main() { int n; for (int i = 0; i < n; i++) { printf("Enter number of elements: "); printf("%d ", arr[i]); scanf("%d", &n); } int *arr = (int*)malloc(n * sizeof(int)); if (arr == NULL) { free(arr); printf("Memory allocation failed!\n"); return 0; return 1; } }  Topic – 7 Analysis of an Algorithm Algorithm Algorithms are the ideas behind computer programs. What is algorithm? : It is a finite set of instruction for performing a particular task. Data structures are implemented using algorithms. The efficient algorithm There is always more than one algorithm to solve particular problem. Now there question out of many choices, which algorithm is to be used? Answer is, for that we need to analysis algorithms. To compare the performance of different algorithm and choose the best one to solve a particular problem, analysis of algorithm is needed. The efficient algorithm What is to be analyzed? Algorithm Analysis Measures 1. Input size 2. Measuring Time complexity 3. Measuring Space complexity 4. Computing Best case, Average case, Worst case 5. Computing order of growth of algorithm. 1. Input size Input size depends on the problem being studied For many problems, such as sorting input size is the number of items in the input—for example, the array size n for sorting. If the input to an algorithm is a graph, the input size can be described by the numbers of vertices and edges in the graph 2. Time complexity The amount of time required by an algorithm to be executed is called its time complexity Time complexity is commonly estimated by counting the number of elementary operations performed on a particular input by the algorithm. Time complexity- Example Time complexity using frequency count for(i=0;i