DS MODULE 1.pdf

DATA STRUCTURES – TYPES AND ADT  Classification of Data Structure Primitive Data Structure Non-Primitive Data Structure  Classification of Data Structure Data structure Primitive DS N...

DATA STRUCTURES – TYPES AND ADT  Classification of Data Structure Primitive Data Structure Non-Primitive Data Structure  Classification of Data Structure Data structure Primitive DS Non-Primitive DS Integer Float Character Pointer  Classification of Data Structure Non-Primitive DS Linear List Non-Linear List Array Queue Graph Trees Link List Stack  Primitive data structures Basic structures that are directly operated upon by the machine instructions. Usually built into the language, such as an integer, a float.  Non-Primitive data structures More sophisticated data structures. Derived from the primitive data structures. Emphasize on structuring of a group of homogeneous (same type) or heterogeneous (different type) data items. Data structures and their representations  Stack Data4 Top Data3 Data2 Data1  Queue Data4 Rear Data3 Data2 Data1 Front List- A Flexible structure that can grow and shrink on demand Head D A M K Temp Nil Head D A M K Temp Nil  Tree Image courtesy: ExamRadar.com Binary Tree, Binary search tree and Heaps Image courtesy: ExamRadar.com  Graph Image courtesy: Medium.com  Abstract Data Type and Data structures Abstract Data Type is the abstraction of data structures which provides the interface which the data structure should adhere too The interface doesn’t specify details about how something has to implement and in which programming language  Abstract Data Type and Data Structure definition Definition:- An ADT is a collection of data and associated operations for manipulating that data A mathematical model, together with various operations defined on the model  ADT Operations Every Collection ADT should provide a way to: Create data structure add an item remove an item find, retrieve, or access an item No single data structure works well for all purposes, and so it is important to know the strengths and limitations of several of them  Example ADT : String Definition: String is a sequence of characters Operations: – StringLength – StringCompare – StringConcat – StringCopy  ADT Syntax : Value Definition Abstract typedef < ParameterType Parameter1, ParameterType Parameter2……, ParameterType ParameterN > ADTType condition:  ADT Syntax : Operator definition Abstract ReturnType OperationName (ParameterType Parameter1, ParameterType Parameter2……, ParameterType ParameterN) Precondition: Postcondition: OR Abstract ReturnType OperationName (Parameter1, Parameter2……, ParameterN) ParameterType Parameter1, ParameterType Parameter2……, ParameterType ParameterN Precondition: Postcondition:  Example ADT : String Value Definition Abstract Typedef StringType Condition: None (A string may contain n characters where n=>0)  Example ADT : String Operator Definition 1. abstract Integer StringLength (StringType String) Precondition: None (A string may contain n characters where n=>0) Postcondition: Stringlength= NumberOfCharacters(String)  Example ADT : String Operator Definition 2. abstract StringType StringConcat( StringType String1, StringType String2) Precondition: None Postcondition: StringConcat= String1+String2 / All the characters in Strings1 immediately followed by all the characters in String2 are returned as result.  Example ADT : String Operator Definition 3. abstract Boolean StringCompare( StringType String1, StringType String2) Precondition: None Postcondition: StringCompare= True if strings are equal, StringCompare= False if they are unequal. (Function returns 1 if strings are same, otherwise zero)  Example ADT : String Operator Definition 4. abstract StringType StringCopy( StringType String1, StringType String2) Precondition: None Postcondition: StringCopy: String1= String2 / All the characters in Strings2 are copied/overwritten into String1.  Example ADT : Rational Number Definition: expressed as the quotient or fraction of two integers, Operations: – IsEqualRational() – MultiplyRationa() – AddRational()  Example ADT : Rational Number Value Definition abstract TypeDef RATIONALType; Condition: RATIONALType !=0; Example ADT : Rational Number Operator Definition abstract abstract RATIONALType RATIONALtype makerational add integer a,b; RATIONALType a,b; Preconditon: b!=0; Precondition: none postcondition : postcondition : makerational =a; add = makerational =b; a*b+b*a add = a * b  Example ADT : Rational Number Operator Definition abstract abstract RetunType? RATIONALType Equal mult RATIONALType a,b; RATIONALType a,b; Precondition: none Precondition: none postcondition equal = postcondition |a * b = = b * a; mult = = a*b mult = = a*b  Abstract Data Types: Advantages Hide the unnecessary details by building walls around the data and operations – o that changes in either will not affect other program components that use them Functionalities are less likely to change Localize rather than globalize changes Help manage software complexity Easier software maintenance Courtsey: https://www.comp.nus.edu.sg/~stevenha/cs1020e/lectures/L5%20- %20ADT.pdf Courtsey: https://www.comp.nus.edu.sg/~stevenha/cs1020e/lectures/L5%20- %20ADT.pdf Courtsey: https://www.comp.nus.edu.sg/~stevenha/cs1020e/lectures/L5%20- %20ADT.pdf Abstract Data Types: Advantages Hide the unnecessary details by building walls around the data and operations  So that changes in either will not affect other program components that use them Functionalities are less likely to change Localise rather than globalise changes Help manage software complexity Easier software maintenance 32  ADT Implementation Computer languages do not provide complex ADT packages. To create a complex ADT, it is first implemented and kept in a library. 12.33  Write Array as ADT Operations: Create Add Delete Sum Search SizeOfArray Thank you 1.1 Introduction to Time complexity, O notation Data Structures and Algorithms  Algorithm: Outline, the essence of a computational procedure, step-by-step instructions  Program: an implementation of an algorithm in some programming language  Data structure: Organization of data needed to solve the problem  Algorithmic problem Specification Specification ? of output as of input a function of input  Infinitenumber of input instances satisfying the specification. For eg: A sorted, non-decreasing sequence of natural numbers of non-zero, finite length:  1, 20, 908, 909, 100000, 1000000000.  3.  Algorithmic Solution Input instance, Algorithm Output adhering to the related to specification the input as required  Algorithm describes actions on the input instance  Infinitely many correct algorithms for the same algorithmic problem  What is a Good Algorithm?  Efficient:  Running time  Space used  Efficiency as a function of input size:  Thenumber of bits in an input number  Number of data elements (numbers, points)  Measuring the Running Time t (ms) 60 50 How should we measure the 40 running time of an algorithm? 30 20 10 Experimental Study 0 50 100 n  Write a program that implements the algorithm  Run the program with data sets of varying size and composition.  Use library function method like clock() to get an accurate measure of the actual running time. Limitations of Experimental Studies  Itis necessary to implement and test the algorithm in order to determine its running time.  Experiments can be done only on a limited set of inputs, and may not be indicative of the running time on other inputs not included in the experiment.  In order to compare two algorithms, the same hardware and software environments should be used. Beyond Experimental Studies We will develop a general methodology for analyzing running time of algorithms. This approach  Uses a high-level description of the algorithm instead of testing one of its implementations.  Takes into account all possible inputs.  Allows one to evaluate the efficiency of any algorithm in a way that is independent of the hardware and software environment.  Pseudo-Code  A mixture of natural language and high-level programming concepts that describes the main ideas behind a generic implementation of a data structure or algorithm.  Eg: Algorithm arrayMax(A, n): Input: An array A storing n integers. Output: The maximum element in A. currentMax←A for i←1 to n-1 do if currentMax < A[i] then currentMax ← A[i] return currentMax Pseudo-Code It is more structured than usual prose but less formal than a programming language  Expressions:  use standard mathematical symbols to describe numeric and boolean expressions  Use ← for assignment (“=” in Java)  use = for the equality relationship (“==” in C)  Method Declarations:  Algorithm name(param1, param2) Pseudo Code  Programming Constructs:  decision structures: if... then... [else... ]  while-loops: while... do  repeat-loops: repeat... until...  for-loop: for... do  array indexing: A[i], A[i,j]  Methods:  calls:object method(args)  returns: return value  Analysis of Algorithms  Primitive Operation: Low-level operation independent of programming language. Can be identified in pseudo-code. For eg:  Data movement (assign)  Control (branch, subroutine call, return)  arithmetic an logical operations (e.g. addition, comparison)  Byinspecting the pseudo-code, we can count the number of primitive operations executed by an algorithm. Example: Sorting INPUT OUTPUT sequence of numbers a permutation of the sequence of numbers a1, a2, a3,….,an b1,b2,b3,….,bn Sort 2 5 4 10 7 2 4 5 7 10 Correctness (requirements for the Running time output) Depends on For any given input the algorithm number of elements (n) halts with the output: how (partially) sorted b1 < b2 < b3 < …. < bn they are b1, b2, b3, …., bn is a algorithm permutation of a1, a2, a3,….,an Insertion Sort A 3 4 6 8 9 7 2 5 1 1 j n i Strategy INPUT: A[1..n] – an array of integers OUTPUT: a permutation of A such that Start “empty handed” A A … A[n] Insert a card in the right position of the already sorted for j 2 to n do hand key A[j] Continue until all cards are Insert A[j] into the sorted sequence inserted/sorted A[1..j-1] i j-1 while i>0 and A[i]>key do A[i+1] A[i] i-- A[i+1] key  Analysis of Insertion Sort cost times for j 2 to n do c1 n key A[j] c2 n-1 Insert A[j] into the sorted sequence A[1..j-1] i j-1 c3 n-1 n while i>0 and A[i]>key c4 j 2 j t c5 n (t j 1) do A[i+1] A[i] j 2 i-- c6 n j 2 (t j 1) A[i+1] ← key c7 n-1 n Total time = n(c1+c2+c3+c7) + j=2 tj (c4+c5+c6) – (c2+c3+c5+c6+c7)  Best/Worst/Average Case n Total time = n(c1+c2+c3+c7) + j=2 tj (c4+c5+c6) – (c2+c3+c5+c6+c7)  Best case: elements already sorted; tj=1, running time = f(n), i.e., linear time.  Worst case: elements are sorted in inverse order; tj=j, running time = f(n2), i.e., quadratic time  Average case: tj=j/2, running time = f(n2), i.e., quadratic time  Best/Worst/Average Case (2)  Fora specific size of input n, investigate running times for different input instances:  Best/Worst/Average Case (3) For inputs of all sizes: worst-case 6n average-case Running time 5n best-case 4n 3n 2n 1n 1 2 3 4 5 6 7 8 9 10 11 12 ….. Input instance size  Best/Worst/Average Case (4)  Worst case is usually used: It is an upper- bound and in certain application domains (e.g., air traffic control, surgery) knowing the worst-case time complexity is of crucial importance  For some algorithms worst case occurs fairly often  Average case is often as bad as the worst case  Finding average case can be very difficult Asymptotic Analysis  Goal: to simplify analysis of running time by getting rid of ”details”, which may be affected by specific implementation and hardware “rounding”: 1,000,001  like 1,000,000  3n2 n2  Capturing the essence: how the running time of an algorithm increases with the size of the input in the limit.  Asymptotically more efficient algorithms are best for all but small inputs  Asymptotic Notation  The “big-Oh” O-Notation  asymptotic upper bound  f(n) = O(g(n)), if there exists constants c and n0, s.t. f(n) c g(n) for n c g(n) n0 f (n) Running Time  f(n) and g(n) are functions over non- negative integers  Usedfor worst-case n0 Input Size analysis Example For functions f(n) and g(n) there are positive constants c and n0 such that: f(n) ≤ c g(n) for n ≥ n0 f(n) = 2n + 6 conclusion: 2n+6 is O(n). Another Example On the other hand… n2 is not O(n) because there is no c and n0 such that: n2 ≤ cn for n ≥ n0 The graph to the right illustrates that no matter how large a c is chosen there is an n big enough that n2 > cn ).  Asymptotic Notation  Simple Rule: Drop lower order terms and constant factors.  50 n log n is O(n log n)  7n - 3 is O(n)  8n2 log n + 5n2 + n is O(n2 log n)  Note:Even though (50 n log n) is O(n5), it is expected that such an approximation be of as small an order as possible Asymptotic Analysis of Running Time  Use O-notation to express number of primitive operations executed as function of input size.  Comparing asymptotic running times  an algorithm that runs in O(n) time is better than one that runs in O(n2) time  similarly, O(log n) is better than O(n)  hierarchy of functions: log n < n < n2 < n3 < 2n  Caution! Beware of very large constant factors. An algorithm running in time 1,000,000 n is still O(n) but might be less efficient than one running in time 2n2, which is O(n2) Example of Asymptotic Analysis Algorithm prefixAverages1(X): Input: An n-element array X of numbers. Output: An n-element array A of numbers such that A[i] is the average of elements X,... , X[i]. for i 0 to n-1 do a 0 for j 0 to i do n iterations i iterations a a + X[j] 1 with A[i] a/(i+1) step i=0,1,2...n- return array A 1 Analysis: running time is O(n2) A Better Algorithm Algorithm prefixAverages2(X): Input: An n-element array X of numbers. Output: An n-element array A of numbers such that A[i] is the average of elements X,... , X[i]. s 0 for i 0 to n do s s + X[i] A[i] s/(i+1) return array A Analysis: Running time is O(n) Asymptotic Notation (terminology)  Special classes of algorithms:  Logarithmic: O(log n)  Linear: O(n)  Quadratic: O(n2)  Polynomial: O(nk), k ≥ 1  Exponential: O(an), a > 1  “Relatives” of the Big-Oh  (f(n)): Big Omega -asymptotic lower bound  (f(n)): Big Theta -asymptotic tight bound 1.1. STATIC AND DYNAMIC IMPLEMENTATION 21-07-2024 2 Objective Explain the static and dynamic implementation of Data structure Interpret its advantages and disadvantages 22-07-2024 3 Static implementation(compile time) of Data Structures Structures whose memory allocated at the start of the program. Structure whose memory allocation is fixed and determined by the compiler at compile time. Structure which do not change its size while programming Eg: Arrays Once to decide the size, they cannot be changed Eg- float a , allocation of 20 bytes to the array, i.e. 5*4 bytes 22-07-2024 4 Static implementation(compile time) of Data Structures advantages Compiler can allocate space during compilation In static data structures, the size of the data structure is known/predicted at compile time. Easy to program Easier to implement. Accessing and modifying the element is straightforward Easy to check for overflow static data structures have a fixed size, making it easier to check for overflow conditions Array allows random access Arrays allow direct access to any element using its index, 22-07-2024 5 Static implementation(compile time) of Data Structures disadvantages Inefficient Use of Memory- Can cause under utilization of memory in case of over allocation That is if you store less number of elements than the number for elements which you have declared memory. Rest of the memory is wasted, as it is not available to other applications. Can cause Overflow in case of under allocation For float a; No bound checking in C for array boundaries, if you are entering more than fives values, It will not give error but when these extra element will be accessed it leads to undefined behaviour. 22-07-2024 6 Static implementation(compile time) of Data Structures disadvantages No reusability of allocated memory Once memory is allocated statically, it cannot be resized or reused, leading to potential wastage if the allocated size is too large Difficult to guess the exact size of the data at the time of writing the program Estimating the exact size of the data at compile time is challenging, leading to risks of under-allocation (causing overflow) or over-allocation (wasting memory). 21-07-2024 7 Dynamic implementation of Data structures Structures that can change size while programming Data structure Linked lists, Binary tree 21-07-2024 8 Runtime or Dynamic Allocation All Linked Data Structures are preferably implemented through dynamic memory allocation. Dynamic data structures provide flexibility in adding, deleting or rearranging data objects at run time. Managed in C through a set of library functions: malloc() Calloc() free() Realloc() 21-07-2024 9 Runtime or Dynamic Allocation Memory space required by Variables is calculated and allocated during execution Get Required chunk of memory at Run time or As the need arises Best Suited – When we do not know the memory requirement in advance, which is the case in most of the real life problems. 21-07-2024 10 Runtime or Dynamic Allocation Efficient use of Memory Additional Space can be allocated at run time. Unwanted Space can be released at run time. Reusability of Memory space 21-07-2024 11 The malloc() fn Allocates a block of memory in bytes The user should explicitly give the block size needed. 21-07-2024 12 The malloc() fn Request to the RAM of the system to allocate memory, If request is granted returns a pointer to the first block of the memory If it fails, it returns NULL 21-07-2024 13 The malloc() fn The type of pointer is Void, i.e. we can assign it any type of pointer. Available in header file alloc.h or stdlib.h 21-07-2024 14 The malloc() fn Syntax- ptr_var=(type_cast*)malloc(size) 21-07-2024 15 The malloc() fn Syntax- ptr_var=(type_cast*)malloc(size) ptr_var = name of pointer that holds the starting address of allocated memory block type_cast* = is the data type into which the returned pointer is to be converted Size = size of allocated memory block in bytes 21-07-2024 16 The malloc() fn Eg- int *ptr; ptr=(int *)malloc(10*sizeof(int)); 21-07-2024 17 The malloc() fn Eg- int *ptr; ptr=(int *)malloc(10*sizeof(int)); Size of int=2bytes So 20 bytes are allocated, Void pointer is casted into int and assigned to ptr 21-07-2024 18 The malloc() fn Eg- char *ptr; ptr=(char *)malloc(10*sizeof(char)); 22-07-2024 19 The malloc() fn- Usage in Linked List 21-07-2024 20 The calloc() fn Similar to malloc It neds two arguments as against one argument in malloc() fn Eg- int *ptr; ptr=(int *)calloc(10,2)); 1st argument=no of elements 2nd argument=size of data type in bytes 21-07-2024 21 The calloc() fn Available in header file alloc.h or stdlib.h 21-07-2024 22 Malloc() vs calloc() fn Initialization: malloc() doesn’t initialize the allocated memory. If we try to access the content of memory block(before initializing) then we’ll get segmentation fault error(or garbage values). calloc() allocates the memory and also initializes the allocated memory block to zero. If we try to access the content of these blocks then we’ll get 0. 21-07-2024 23 Malloc() vs callloc() fn Malloc allocate a single large block of memory with the specified size. Calloc allocate multiple blocks of memory dynamically allocate the specified number of blocks of memory of the specified type. 21-07-2024 24 The free() fn Used to deallocate the previously allocated memory using malloc or calloc() fn Syntax- free(ptr_var); ptr_var is the pointer in which the address of the allocated memory block is assigned. Returns the allocated memory to the system RAM.. 21-07-2024 25 What happens when you don’t free memory after using malloc() 21-07-2024 26 What happens when you don’t free memory after using malloc() The memory allocated using malloc() is not de-allocated on its own. So, “free()” method is used to de-allocate the memory. But the free() method is not compulsory to use. 21-07-2024 27 What happens when you don’t free memory after using malloc() If free() is not used in a program the memory allocated using malloc() will be de- allocated after completion of the execution of the program (included program execution time is relatively small and the program ends normally). 22-07-2024 28 What happens when you don’t free memory after using malloc() Still, there are some important reasons to free() after using malloc(): 1) Use of free after malloc is a good practice of programming. 2) Efficient memory usage. 3) Prevents memory leaks (A memory leak occurs when a program loses the reference to allocated memory without freeing it. This results in the memory being unusable for the duration of the program) 21-07-2024 29 The realloc() fn To resize the size of memory block, which is already allocated using malloc. Used in two situations: If the allocated memory is insufficient for current application If the allocated memory is much more than what is required by the current application 21-07-2024 30 The realloc() fn Syntax- ptr_var=realloc(ptr_var,new_size); ptr_var is the pointer holding the starting address of already allocated memory block. Available inn header file Can resize memory allocated previously through malloc/calloc only. 21-07-2024 31 Eg of malloc() fn #include #include #include int main() { char *mem_allocation; mem_allocation = (char *) malloc( 20 * sizeof(char) ); if( mem_allocation == NULL ) { printf("Couldn't able to allocate requested memory\n"); } else { strcpy( mem_allocation,“ABCD"); } 21-07-2024 32 Eg of malloc() fn printf("Dynamically allocated memory content : "%s\n", mem_allocation ); mem_allocation=realloc(mem_allocation,100*sizeof(char)); if( mem_allocation == NULL ) { printf("Couldn't able to allocate requested memory\n"); } else { strcpy( mem_allocation,"space is extended upto 100 characters"); } printf("Resized memory : %s\n", mem_allocation ); free(mem_allocation); } 22-07-2024 33 Advantages of Dynamic Data structures Efficient Memory Utilization: Dynamic data structures only use the space needed at any time. Memory is allocated when needed and deallocated when not in use, leading to efficient memory utilization. Adaptability and Flexibility: They can grow and shrink at runtime, making them adaptable to varying data sizes, which is crucial for applications with unpredictable or frequently changing data requirements. Reclaiming Unused Memory: Storage that is no longer used can be returned to the system for other uses, helping manage overall memory usage and improving the application's efficiency. 22-07-2024 34 Dis advantages of Dynamic Data structures Difficult to progam More complex implementation and management compared to static data structures. Can be slow to implement searches Slower access times due to pointer referencing and dynamic memory management. A linked list allows only serial access 21-07-2024 35 Which part of the memory is allocated when static memory allocation is used, for int,char,float,arrays,struct,unions…..? Which part of the memory is allocated when malloc and calloc are called for any variable? ?? 21-07-2024 36 Stack and Heap Stack and Heap both stored in the computer's RAM. 22-07-2024 37 Stack Basic type variables such as int, double, etc, and complex types such as arrays and structs. These variables are put on the stack in C. The stack is a region of memory that stores temporary variables created by each function. When a function is called, a stack frame is created which contains: Function parameters: The values passed to the function. Local variables: Variables declared within the function. Return address: The address of the next instruction to execute after the function call. There is a limit (varies with OS) on the size of variables that can be stored on the stack. 22-07-2024 38 Heap The heap is a region of memory used for dynamic memory allocation. Unlike the stack, the heap does not have a strict organization like LIFO. Memory can be allocated and freed at any time, in any order. 22-07-2024 39 Stack vs Heap Stack – Heap Size: Generally small and fixed. Size: Can be much larger than the stack. It grows as needed (up to system The size is determined at the limits). start of the program. Speed: Slower access compared to the stack, because memory management Speed: Very fast access, as it is on the heap is more complex. managed by the CPU. Scope: Variables on the heap are Scope: Variables on the stack accessible from anywhere in the program as long as you have a pointer are only accessible within the to them. function they are declared in. Lifetime: Variables persist until explicitly deallocated using free() (or Lifetime: Variables are the program ends). They are not destroyed when the function call automatically destroyed when a completes. function exits. Usage: Used for dynamic memory Usage: Used for function call allocation where the size or lifetime of management, local variables, the data cannot be determined at compile time. and temporary data. Data Structures Ms. Jyothi Rao [email protected]  Data structures: What and Why? Data structure is a way of storing and organizing data in a computer so that it can be retrieved and used most productively. Different kinds of data structures are meant for different kinds of applications, and some are highly specialized to specific tasks. Where might we need data structures?  Why Data structures? They help to manage ,organize data and process data in volatile/temporary memory Essential ingredient in creating fast and powerful algorithms Program = Algorithm + Data structure They make the code cleaner and easier to understand Data structures Vs Database Vs knowledgebase!!  Which Data structures? Stack - LIFO Queue- FIFO, Queue, Circular queue, Dequeue, Priority queue Linked lists- singly linked list, doubly linked list, circular linked list Graph Trees – General trees, binary trees, binary search trees, B tree, B+ tree, heaps, AVL trees Set, map, dictionary  Data structures in real life? A Queue for bus Waiting in clinic or office Maps, geographical or railway maps etc Social networks Undo operation in any s/w or app Operating system processes Evaluate an equation Games like chess, tic-tac-toe Family history Books Lab Work  Lab assessment Rubrics Timely Quality of the execution of code (Correct Quality and code and program with originality of write- On- submission of comments and Originality of Understanding up, including the LAB scree Attendance write-up output) code of concepts post lab questions Total n test Total 5 5 5 5 5 5 30 20 50  Programming language C language Why??? Low-level memory access, Performance, pointer-arithmetic, simplicity, widely supported etc.  Internal Assessments Sr. No. Task Description of task Schedule 1 Rapid Fire activity with Every student has to prepare 10 flash cards on data structures in After flash cards module 1, 2 and 3.1 Test 2 Peer grading This can be done in a group of 2-3 students. First Programming 1.Small programming programs will be assigned to each group. Week of assignment using a data 2.The presentation screencast video should- explain the problem Oct structure to develop statement, logic, code and output. solution for a small 3.The video duration will be max 10mins application 4.All students must participate in presentation 5.Students would choose a problem statement and suggest one of the data structure for developing the solution, and how the solution will be implemented. Upon teacher’s approval, students would work on the chosen problem and submit their work. 6.Code submission will be on Turnitin platform to check plagiarism and originality.  Test Module 1- Introduction , Types of Data Structures, ADT (Abstract data type) Module 2 - Linear data structure (linked list, stack and queue) Module 3.1 – Nonlinear data structure (Tree) Evaluation Scheme Theory Evaluation Scheme Lab  Modes of Content Delivery Blackboard Teaching Visual Aids Seminar NPTEL Video Lectures Quiz Guest Lecture Test Assignments/Activities Queries??? Thank you!!  Application of Data Structures 9/19/2024 Applications of stack: Expression evaluation and syntax parsing Balancing of symbols, paranthesis Infix to Postfix /Prefix conversion Reverse a String using Stack Redo-undo features at many places like editors, photoshop. Forward and backward feature in web browsers Used in many algorithms like Tower of Hanoi, tree traversals, stock span problem, histogram problem. 9/19/2024  Applications of stack: Backtracking – Backtracking is an algorithmic-technique for solving problems recursively by trying to build a solution incrementally, one piece at a time, removing those solutions that fail to satisfy the constraints of the problem at any point of time – Other applications can be Backtracking, Knight tour problem, rat in a maze, N queen problem and sudoku solver 9/19/2024  Backtracking-Finding the correct path in a maze. There are a series of points, from the starting point to the destination. We start from one point. To reach the final destination, there are several paths. Suppose we choose a random path. After following a certain path, we realise that the path we have chosen is wrong. So we need to find a way by which we can return to the beginning of that path. 9/19/2024  Backtracking-Finding the correct path in a maze. This can be done with the use of stacks. With the help of stacks, we remember the point where we have reached. This is done by pushing that point into the stack. In case we end up on the wrong path, we can pop the top point from the stack and thus return to the last point and continue our quest to find the right path. 9/19/2024  Applications of stack: Depth-first search – The prototypical example of a backtracking algorithm is depth-first search, which finds all vertices of a graph that can be reached from a specified starting vertex. In Graph Algorithms like Topological Sorting and Strongly Connected Components 9/19/2024  Applications of stack: Compile time memory management Almost all calling conventions‍ 9/19/2024  Function calls using stack  Compile time memory management  A number of programming languages are stack-oriented,  meaning they define most basic operations as taking their arguments from the stack, and placing any return values back on the stack.  Eg- adding two numbers, printing a character 9/19/2024  Function calls using stack Stacks are an important way of supporting nested or recursive function calls. 9/19/2024  Function calls using stack The‍ways‍in‍which‍subroutines‍ receive‍their‍parameters‍and‍ return‍results‍—use a special stack (the "call stack") 9/19/2024  Function calls using stack Call stack holds information about procedure/function calling and nesting in order to switch to the context of the called function and restore to the caller function when the calling finishes. 9/19/2024  Queues 9/19/2024  Real life Examples of Queue The people standing in a railway reservation row are an example of queue. Each new person comes and stands at the end of the row (rear end of queue) and persons getting their reservations confirmed , get out of the row from the front end. 9/19/2024  Real life Examples of Queue Our software queues have counterparts in real world queues. We wait in queues – to buy pizza, – to enter movie theaters, – to drive on a turnpike, and – to ride on a roller coaster. 9/19/2024  Applications of Queue: Queues are widely used as waiting lists for a single shared resource like printer, disk, CPU. Disk Scheduling 9/19/2024  Applications of Queue: CPU scheduling- When multiple processes require CPU at the same time, various CPU scheduling algorithms are used which are implemented using Queue data structure. 9/19/2024  Applications of Queue: CPU scheduling- 9/19/2024  Applications of Queue: When things‍don’t‍have‍to‍be‍processed‍immediately, but have to be processed in First In First Out order like Breadth First Search. When data is transferred asynchronously (data not necessarily received at same rate as sent) between two processes. Examples include IO Buffers, pipes, file IO, etc. Queue are used to maintain the play list in media players in order to add and remove the songs from the play-list. Courtesy:https://www.javatpoint.com/data-structure-queue 9/19/2024  Queue Example Accessing printer in multiuser environment- ❑ If a printer is in process and more than one user wants to access the printer then ❑ it maintains the queue for user requesting access and serves in FIFO manner for giving access. 9/19/2024  Applications of Tree Data Structure Store hierarchical data, like folder structure, organization structure, XML/HTML data. Binary Search Tree is a tree that allows fast search, insert, delete on a sorted data. It also allows finding closest item Heap is a tree data structure which is implemented using arrays and used to implement priority queues. 9/19/2024  Applications of Tree Data Structure B-Tree and B+ Tree : They are used to implement indexing in databases. Syntax Tree: Used in Compilers. Spanning Trees and shortest path trees are used in routers and bridges respectively in computer networks 9/19/2024  Applications of Tree Data Structure Trie : Used to implement dictionaries with prefix lookup. 9/19/2024  Applications of Graph Data Structure Google maps Facebook World Wide Web Operating System 9/19/2024  Applications of Graph Data Structure In Computer science graphs are used to represent the flow of computation. Google maps – – uses graphs for building transportation systems, – where intersection of two(or more) roads are considered to be a vertex and – the road connecting two vertices is considered to be an edge, – thus their navigation system is based on the algorithm to calculate the shortest path between two vertices. 9/19/2024  Social Network Analysis In Facebook, – users are considered to be the vertices and – if they are friends then there is an edge running between them. – Facebook’s‍Friend suggestion algorithm uses graph theory. – Facebook is an example of undirected graph. 9/19/2024  Social Network Analysis So, for Facebook, we can think of a node as a friend and the edge as the relationship that links the friends together. Below is a basic illustration of some friends in a network: 9/19/2024  Social Network Analysis From here we can start to measure centrality of the graph or the influence among friends. 9/19/2024  Social Network Analysis 9/19/2024  Social Network Analysis Degree centrality is a calculation of how many direct friends that any individual friend in the network has. Friends with a high degree of centrality are not necessary the most powerful or influential, but they act as hubs within the network. 9/19/2024  Social Network Analysis Brenda is acting as the hub in this social network since she has the most connections or highest degree within the network. 9/19/2024  Social Network Analysis Closeness Centrality- Calculates the shortest paths between all nodes, then assigns each node a score based on its sum of shortest paths. When to use it: For finding the individuals who are best placed to influence the entire network most quickly. Closeness‍centrality‍can‍help‍find‍good‍‘broadcasters’ 9/19/2024 Applications of Graph Data Structure In World Wide Web, – web pages are considered to be the vertices. – There is an edge from a page u to other page v if there is a link of page v on page u. – This is an example of Directed graph. – It was the basic idea behind Google Page Ranking Algorithm. 9/19/2024 Applications of Graph Data Structure In Operating System, – we come across the Resource Allocation Graph where each process and resources are considered to be vertices. 9/19/2024 Applications of Graph Data Structure Edges are drawn from – resources to the allocated process, or – from requesting process to the requested resource. If this leads to any formation of a cycle then a deadlock may occur. 9/19/2024  Resource Allocation Graph With A Deadlock Suppose P3 requests for R2, Since no resource instance is free, a request edge P3->R2 is added So, Now Two cycles exist – P1->R1->P2->R3->P3->R2->P1 P2->R3->P3->R2->P2 P1,P2,P3 are deadlocked 9/19/2024