Data Structure and Algorithm (BCSE202L) Lecture Notes PDF

Data Structure and Algorithm: (BCSE202L) Introduction DSA: Dr. Durgesh Kumar S C O P E , V I T Ve l l o r e Durgesh Kumar (VIT Vellore)...

Data Structure and Algorithm: (BCSE202L) Introduction DSA: Dr. Durgesh Kumar S C O P E , V I T Ve l l o r e Durgesh Kumar (VIT Vellore) Week 1: Lecture 01  Lecture Outline ❑ Introduction to DSA ❑ What is Data Structure? ❑ Examples of Different data structure? ❑ Classification of different data structures as linear and non-linear. Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19  GOALS ❑ Categorize and differentiate different data structure as linear and non-linear data structure. Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19  What is Data Structure? ❑ Data structure is a storage that is used to store and organize data. ❑ It is a way of arranging data on a computer so that it can be accessed and updated efficiently. ❑ Array Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19  Data Structure Examples? ❑ Array ❑ Link List Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19  Data Structure Examples ❑ Array, Link List ❑ Stack - Last In First Out (LIFO) - top will point to index/address of last element. Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19  Data Structure Examples ❑ Array, Link List, Stack ❑ Queue - First In First Out (FIFO) - Two pointers front and rear for two ends. Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19  Data Structure Examples ❑ Array, Link List, Stack, Queue – Module 2 ❑ Tree ❑Module 4 o Root node o Parent, child node, o Leaf node Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19  Data Structure Examples ❑ Array, Link List, Stack, Queue – Module 2 ❑ Tree ❑Module 4 o Root node o Parent, child node, o Leaf node o Binary Search Tree (BST) - Insertion - Deletion - Finding min, max element - Finding kth min, kth max element. Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19  Data Structure Examples ❑ Array, Link List, Stack, Queue, Tree ❑ Graph ❑Module 5 o Nodes, Edges o BFS, DFS o Minimum distance between two nodes. o Minimum Spanning tree - Prim’s and Kruskal Algorithm o Shortest path o Dijkstra’s Algorithm Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19  Data Structure Examples ❑ Array, Link List, Stack, Queue, Tree, Graph ❑ Hashing Module 6 o 51%10 = 1 o 12%10 = 2 o 74%10 =4 Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19  Data Structure Examples ❑ Array, Link List, Stack, Queue, Tree, Graph, Hashing ❑ Heaps, AVL Module 7 Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19  Data Structure Examples ❑ Array, Link List, Stack, Queue, Tree, Graph, Hashing ❑ Heaps, AVL Module 7 -Balanced Tree - Insert a node - Delete a node - AVL rotations Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19  Data Structure classification Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19  Summary ❑ Examples of Different Data structures ❑ Stack, Queue, Link list ❑ Tree, Graph, Hashing ❑ AVL Tree, Heap ❑ Linear vs Non-linear data structure Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19  Next Class ❑ Algorithm Analysis ❑ Time and space complexity ❑ Best case, Worst case, Average case ❑ Asymptotic analysis: Big O, Theta, Omega ❑ Linear vs Non-linear data structure Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19 Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19 Data Structure and Algorithm: (BCSE202L) Introduction to Algorithm DSA: Dr. Durgesh Kumar Assistant Professor (Senior), S C O P E , V I T Ve l l o r e Durgesh Kumar (VIT Vellore) Week 1: Lecture 01  Lecture Outline ❑ Introduction to Algorithm ❑ What is Algorithm? ❑ Examples of Different Algorithm? ❑ Why to study Algorithms? ❑ Algorithm used of different field. ❑ Measuring the algorithm. Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19  GOALS ❑ Understand and appreciate different algorithms linear and its usage in real life. Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19  What is Algorithm? ❑ Algorithm (Noun): A set of steps to a accomplish a particular task. Examples ❑ Algorithm to get to PRP 110 from your room. ❑ To choose a gadgets (Mobile/PC/ Tablets) to buy. ❑ Finding a book in library. ❑ Getting maximum like/follower on a Tiktok/ Instagram. ❑ Getting a match on tinder. ❑ Algorithm for self-driving cars. Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19  Algorithms Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19  Why study Algorithms ❑ Finding good algorithms ❑ And knowing when to apply them will help you write good and interesting programs! We will see few famous algorithm now! Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19 Examples of interesting Algorithms ❑ How does google Hangout/Microsoft team transmit live video over internet so quickly. Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19 Examples of Interesting Algorithms ❑ How does google Hangout/Microsoft team/StarSports/Zoom transmit live video over internet so quickly. ❑ They use audio and video compression algorithm. Video Compression | Audio Compression Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19  Examples of Interesting Algorithms ❑ How does google Map figure out path from location 1 (India Gate Delhi) to location 2 (VIT Main Gate). Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19  Examples of Interesting Algorithms ❑ Route Finding Algorithm: Dijkstra’s Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19  Examples of Interesting Algorithms ❑ Route Finding Algorithm: Dijkstra’s Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19  Examples of Interesting Algorithms ❑ Route Finding Algorithm: Dijkstra’s Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19  Examples of Interesting Algorithms ❑ Route Finding Algorithm: Dijkstra’s Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19  Examples of Interesting Algorithms ❑ Route Finding Algorithm: Dijkstra’s Shortest Path : C -> E-> F -> H Cost : 5 Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19  Examples of Interesting Algorithms ❑ How does PiXAR color a 3-D of a character based on lighting in the room. Link ❑ They use a rendering algorithm. Flat Shading | Phong Shading Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19  Examples of Interesting Algorithms ❑ How does NASA choose how to rearrange solar panels on the Internet space station, and when to re-arrange them. ❑ They use a Optimization and Scheduling algorithm. Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19 Examples of Interesting Algorithms ❑ Auto complete while typing a message. ❑ Spelling and the Grammar checking. Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19 Examples of Interesting Algorithms ❑These algorithms are more complex then day to day algorithms. ❑ But they boil down to same things – A set of steps to accomplish a task. Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19  Which Algorithms to apply? ❑ If you know something about existing algorithms, you may save some effort. ❑ And make your program faster by applying the right ones. Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19  Algorithms Design? ❑ Suppose you are designing a computer game with computer as one player. ❑ You can look at checkers game. Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19  Algorithms Design- Computer Game? Checkers game. Min Max Algorithm Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19  Algorithms Design- Computer Game? Checkers game. YOUR GAME ? ❑If your game is similar to checkers game, you may reuse similar algorithms. ❑ If not, then knowing limitations might lead you to re-design your game. Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19  What Algorithms you can create? ❑ It is important to know How to design new algorithms?. ❑ as well as, how to analyze their correctness and efficiency. Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19 Application of Algorithm – Biological Science Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19 Application of Algorithm – Biological Science ❑ Designing new algorithm that help designing new molecular structure, that are at core of disease finding drug. Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19 Application of Algorithm – Geotech (Civil) Climate and Weather prediction algorithm. Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19  Application of Algorithm – Astronomy Finding a new star in Universe Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19 Application of Algorithm – Data Analysis Analysing huge data of Universe ❑ Hubble telescope of NASA transmits about 150 GB of raw science data every week. Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19  Application of Algorithm Algorithms are everywhere ❑ Finance ❑ Mathematics ❑ Physics ❑ Humanities ❑ Civil Engineering ❑ Art ❑ Bio Medical ❑ Medicine ❑ Computer Science ❑ Mathematics ❑ Nano technology ❑ Macro economics ❑ Astronomy ❑ Cryptograpgy ❑ Data Analysis ❑ Programming ❑ Machine Learning Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19  What makes a good Algorithm? Analysis of Algorithm 1. Correctness 2. Efficiency Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19  What makes a good Algorithm? Analysis of Algorithm 1. Correctness 2. Efficiency ❑ Most of the time, we want an algorithm to give correct answer (Correctness). ❑ Sometime we can live with an algorithm which does not give correct or best answer. ❑ Because the perfect algorithm in that case takes a really really long time. Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19  What makes a good Algorithm? Analysis of Algorithm - TSP ❑ 1 truck/ person ❑ 7 locations Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19  What makes a good Algorithm? Analysis of Algorithm - TSP ❑ The Truck/Person has to start and end at same location (A). ❑ He has to visit every cities exactly once. ❑ Find the optimal path (order of visit to different cities). Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19  What makes a good Algorithm? Analysis of Algorithm - TSP ❑ 1 truck/ person ❑ 7 locations ❑ Total possible path = 7! = ❑ for 25 cities = 25! = 620, 448, 401, 733, 239, 439, 360, 000 path ❑ In some case, good is good enough. Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19  What makes a good Algorithm? Analysis of Algorithm - TSP # of nodes Neares Brute force t insertio n 1 1 1 2 4 1 3 9 2 4 16 6 … 25 625 620,448,733,239, 439, 360,000 n n2 n! ❑ In some case, good is good enough. Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19  Analysis of Algorithm? How to measure Algorithm Efficiency ? Algorithm ❑ We can measure the how long it takes to run a code. ❑ It would tell us only about that particular implementation in a certain programming language on a particular input. Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19  Analysis of Algorithm? How to measure Algorithm Efficiency ? Run time Program P1 Analysis 25 locations Programmers style of writing Programming Lang. i-7 16 GB RAM Input size Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19  Analysis of Algorithm? How to measure Algorithm Efficiency ? ❑ Instead Computer scientist have devised a new approach called Asymptotic analysis of algorithm. ❑ It is independent of previous factors. Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19 Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19 Data Structure and Algorithm: (BCSE202L) STACK Implemention DSA: Dr. Durgesh Kumar Assistant Professor (Senior), S C O P E , V I T Ve l l o r e Durgesh Kumar (VIT Vellore) Week 1: Lecture 01  Lecture Outline ❑ Implementation of STACK in C ❑ Stack and it’s properties ❑ STACK ADT ❑ Functions defined on STACK ❑ Implementation of init_STACK function ❑ Implementation of push function ❑ Implementation of show_stack function ❑ Implementation of pop function ❑ Implementation of check_overflow function ❑ Implementation of check_underflow function. ❑ Implementation of check_top function ❑ Implementation of delete_STACK function Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19  GOALS ❑ Implementation of STACK in C ❑ Using STACK to check the balance of parenthesis. (, } ] etc. In Next class/lab: ❑ Using STACK evaluation of expression. ❑ 2+ 3*(5 +7) ❑ Conversion of infix to postfix expression. ❑ Conversion of infix to prefix expression. Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19  STACK ❑ One end is closed. ❑ Only one end is open for Insertion or deletion of element. ❑ top points to index/address of the top most element. ❑ Last In First Out (LIFO) is followed. Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19  Preliminaries Data Types Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 03 2 /19  Preliminaries Data Types // To declare an //To define a user-defined data integer variable type) int x; struct student x = 5; { char name; int reg_num; }; struct student s1; s1. name =“Akash\0”; s1. reg_num = 22402; Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 03 2 /19  Preliminaries Data Types - structure //user-defined data- student struct student // To declare a structure { char name; pointer int reg_num; struct student *s2; }; s2->name=“Sam\0”; struct student s1; s2->reg_num =22BCE221; s1. name =“Akash\0”; s1. reg_num = 22BCS402; Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 03 2 /19  Preliminaries Data Types in C/C++ Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 03 2 /19  Preliminaries Abstract Data Type ❑ Primitive Data types such as int, float, double, long, etc. are in-built datatypes. ❑ Basic operations with them such as addition, subtraction, division, multiplication, etc. is already defined. ❑ We can define user defined data types using struct, enum, union, and class. ❑ What about the set of operations supported on them? Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 03 2 /19  Preliminaries Abstract Data Type ❑ To simplify the process of solving problems, we combine the user- defined data structures with their operations, and this is called Abstract Data Types (ADT). ❑ Abstract Data types has two parts: a. Declaration of data b. Declaration of operations – rule governing the operations such as LIFO, FIFO, constraint of BST. Basic operations with them such as addition, subtraction, division, multiplication, etc. is already defined. ❑ Examples of ADT’s are STACK, QUEUE, LINK LIST, and BST. ❑ Implementation of operations on ADT are left to users. Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 03 2 /19  Preliminaries Examples of ADT -STACK Declaration of STACK ADT s is a pointer to mySTACK (user- defined) type of variable. typedef struct STACK typedef is used to alias struct STACK { to mySTACK. int *array; So we don’t need to type struct int max_size; STACK every where while declaring int top; the variable of type struct STACK. } mySTACK; Instead of mySTACK *s; struct STACK *s; // To access Element We can write s->A; mySTACK *s; s->top; Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 03 2 /19  Preliminaries Examples of ADT -STACK Declaration of STACK ADT typedef struct STACK { int *array; int max_size; int top; } mySTACK; mySTACK *s; // To access Element s->A; s->top; Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 03 2 /19  Preliminaries Examples of ADT -STACK // Declaration of Declaration of Operations on STACK ADT STACK ADT Rule : LIFO ( Last In First Out) typedef struct STACK { i) mySTACK * init_stack ( int max_size); int *A; ii) void push (mySTACK *s, int x); int max_size; iii) int pop(mySTACK *s); int top; iv) void show_stack(mySTACK *s ); } mySTACK; v) int get_top(mySTACK *s); mySTACK *s; // To access Element s->A; s->top; Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 03 2 /19  STACK implementations in C Implementation of STACK ADT functions mySTACK * init_stack(int max_size) Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 03 2 /19  STACK implementations in C Implementation of STACK ADT functions mySTACK * init_stack(int max_size) Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 03 2 /19  STACK implementations in C Implementation of STACK ADT functions mySTACK * init_stack(int max_size); Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 03 2 /19  STACK implementations in C Implementation of STACK ADT functions void push(mySTACK *s, int x); Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 03 2 /19  STACK implementations in C Implementation of STACK ADT functions void show_stack(mySTACK *s); Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 03 2 /19  STACK implementations in C Implementation of STACK ADT functions int pop(mySTACK *s) Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 03 2 /19  STACK implementations in C Implementation of STACK ADT functions int get_top(mySTACK *s) Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 03 2 /19  STACK implementations in C Implementation of STACK ADT functions int delete_stack(intmySTACK *s) Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 03 2 /19  STACK implementations in C Implementation of STACK ADT functions Check complete basic code of STACK at github repo: https://github.com/durgeshbhagat/DSA/blob/main/M odule_2/Stack/stack_basic.c Check STACK code part-2 with UNDERFLOW and OVERFLOW condition in the github link: https://github.com/durgeshbhagat/DSA/blob/main/M odule_2/Stack/stack_01.c Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 03 2 /19  STACK implementations in C Assignment 1. Create a STACK with character array and implement all the functions of STACK. a. init_STACK b. push c. pop d. Print_STACK Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 03 2 /19  STACK implementations in C Assignment 2. WAP using STACK to check whether the pairs and the orders of “{“, “}”, “(“, “)”, “[“, “]” are correct in the given string expression. Input: exp = “[()]{}{[()()]()}” Output: Balanced Explanation: all the brackets are well-formed Input: exp = “[(])” Output: Not Balanced Explanation: 1 and 4 brackets are not balanced because there is a closing ‘]’ before the closing ‘(‘ Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 03 2 /19 Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19 Data Structure and Algorithm: (BCSE202L) Analysis of Algorithm DSA: Dr. Durgesh Kumar Assistant Professor (Senior), S C O P E , V I T Ve l l o r e Durgesh Kumar (VIT Vellore) Week 1: Lecture 01  Lecture Outline ❑ Introduction to data types ❑ Primitive vs user-defined data types? ❑ Data types in C/C ++? ❑ What is ADT? ❑ STACK ADT examples ❑ Analysis of Algorithm ❑ Rate of Growth ❑ Commonly used rate of growth and comparison ❑ Big-O, Omega, Theta ❑ Finding g(n), c, and no for given f(n) ❑ Common guidelines for finding Asymptotic analysis of algorithm Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19  GOALS ❑ Understand and appreciate different algorithms and its usage in real life. Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 01 2 /19  Preliminaries Data Types Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 03 2 /19  Preliminaries Data Types // To declare an //To define a user-defined data integer variable type) int x; struct student x = 5; { char name; int reg_num; }; struct student s1; s1. name =“Akash\0”; s1. reg_num = 22402; Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 03 2 /19  Preliminaries Data Types - structure //user-defined data- student struct student // To declare a structure { char name; pointer int reg_num; struct student *s2; }; s2->name=“Sam\0”; struct student s1; s2->reg_num =22BCE221; s1. name =“Akash\0”; s1. reg_num = 22BCS402; Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 03 2 /19  Preliminaries Data Types in C/C++ Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 03 2 /19  Preliminaries Abstract Data Type ❑ Primitive Data types such as int, float, double, long, etc. are in-built datatypes. ❑ Basic operations with them such as addition, subtraction, division, multiplication, etc is already defined. ❑ We can define user defined data types using struct, enum, union, and class. ❑ What about the set of operations supported on them? Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 03 2 /19  Preliminaries Abstract Data Type ❑ To simplify the process of solving problems, we combine the user- defined data structures with their operations, and this is called Abstract Data Types (ADT). ❑ Abstract Data types has two parts: a. Declaration of data b. Declaration of operations – rule governing the operations such as LIFO, FIFO, constraint of BST. Basic operations with them such as addition, subtraction, division, multiplication, etc. is already defined. ❑ Examples of ADT’s are STACK, QUEUE, LINK LIST, and BST. ❑ Implementation of operations on ADT are left to users. Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 03 2 /19  Preliminaries Examples of ADT -STACK Declaration of STACK ADT Declaration of Operations on STACK ADT typedef struct STACK { Rule : LIFO ( Last In First Out) int A; int top; i) void init_stack (mySTACK *s); }mySTACK; ii) void push (mySTACK *s, int x); iii) int pop(mySTACK *s); mySTACK *s; iv) void show_stack(mySTACK *s ); // To access Element v) int get_top(mySTACK *s); s->A; s->top; Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 03 2 /19  Preliminaries Rate of Growth ❑ Suppose you invested Rs 1000, you got Rs 2000 after 5 years. What is Annualized Return On Investment (ROI) ? 14.87% ❑ Suppose you invested Rs 10000, you got Rs 15000 after 5 years. Annualized Return On Investment (ROI) ? – 8.45 % ❑ Which one is better investment ? Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 03 2 /19  Preliminaries Commonly used rate of growth S.No Time Complexity Name Use case ( Worst Case) 1 1 Constant s 2 log(n) Logarithmic Binary Search 3 n Linear Linear Search, sum of array 4 n log(n) Linear Sorting: Quick sort, Merge sort logarithmic 5 n2 Quadratic Sorting: Bubble sort, Insertion sort, Selection sort 6 n3 Cubic Matrix Multiplication A(M*N) * B(N*P) 7 2n Exponential Fibonacci series 8 n! Factorial Travelling Salesman Problem (TSP) Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 03 2 /19  Preliminaries Comparison of Commonly used logarithm 1)NN > N! > 2N > N3 > N2 > NlogN > N> logN > 1 Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 03 2 /19  Preliminaries Commonly used series sum 1. Arithmetic series 1 + 2+ 3 +.. + n = n(n+1) /2 2. Geometric series 1 + x + x2 + x3 + …+ xn = (xn+1 – 1) (x-1) , x!=1, x>1 3. Harmonic Series Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 03 2 /19  Asymptotic Analysis Different types of Asymptotic analysis 1. Big-O (Upper Bound) 2. Omega-Ω (Lower Bound) 3. Theta-ϴ (Tight Bound) Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 03 2 /19  Asymptotic Analysis Big-O ( Upper Bound) Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 03 2 /19  Asymptotic Analysis Big-O ( Upper Bound) ❑ Given f(n) ❑ Upper Bound can be written as g(n) ❑ if c g(n) >= f(n) for all n > n0 - c and n0 are +ve real constants ❑ f(n) = O( g(n) ) Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 03 2 /19  Asymptotic Analysis Big-O ( Upper Bound) ❑ Given f(n) = 3n^2 + 6n + 8 ❑ What can be g(n)? ❑ - g(n) ? ❑ n^3 ❑ Can G(n) = n^2 ? Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 03 2 /19  Asymptotic Analysis Big-O ( Upper Bound) ❑ Given f(n) = 3n^2 + 6n + 8 ❑ What can be g(n)? ❑ - g(n) ? ❑ n^3 ❑ Can G(n) = n^2 ? Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 03 2 /19  Asymptotic Analysis Big-O ( Upper Bound) ❑ Given f(n) = n^4 + 100 n^2 + 50n + 200 ❑ What can be g(n)? ❑ What will be value of c and no ? Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 03 2 /19  Asymptotic Analysis Big-O ( Upper Bound) ❑ Given f(n) = 2n^3 - 3 n^2 ❑ What can be g(n)? ❑ What will be value of c and no ? ❑ Non-uniqueness of c and no Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 03 2 /19  Asymptotic Analysis Big-O ( Upper Bound) ❑ Given f(n) = 2^n + n^2 +n log(n) + 50 n+ 8 ❑ 2^n > n^2 > n log(n) > 50 n > 8 ❑ G (n) = 2^n ❑ G(n) = n! ❑ G(n) = 3^n - For all these we can find positive real constant c, no - Such that c* g(n) >= f(n) ❑ What will be value of c and no for each of g(n) ? Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 03 2 /19  Big-O Exercise Find the Big-O (g(n)) with c and n0 for following f(n) i) 2n^3 - 2n^2 ii) n^2 + 1 iii) n^2 + log(n) + 2*n + 20 iv) n! + 2^n + n^4 + 100 v) n^2 + n log(n) + 50  Big-O Exercise Q: Find the Big-O (g(n)) with c and n0 for following f(n) f(n) = 4*n^3 + 3*n^2 + 50 g(n) = 2^n + 1000 Is f(n) = O(g(n)) True? For c=2, what would be value of n0? Intersection of f(n) and g(n) not needed a/c to definition of Big-O.  Big-O Exercise Find the Big-O (g(n)) with c and n0 for following f(n) i) 2n^3 - 2n^2 ii) n^2 + 1 iii) n^2 + log(n) + 2*n + 20 iv) n! + 2^n + n^4 + 100 v) n^2 + n log(n) + 50  Asymptotic Analysis Omega Ω (Lower Bound) Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 03 2 /19  Asymptotic Analysis Omega Ω (Lower Bound) ❑ Given f(n) ❑ Lower Bound Ω can be written as g(n) ❑ if c g(n) n0 - c and n0 are +ve real constants ❑ f(n) = Ω( g(n) ) Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 03 2 /19  Asymptotic Analysis Omega Ω (Lower Bound) ❑ Given f(n) ❑ Lower Bound Ω can be written as g(n) ❑ if c g(n) n0 - c and n0 are +ve real constants ❑ f(n) = Ω( g(n) ) Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 03 2 /19  Asymptotic Analysis Omega Ω (Lower Bound) ❑ Find lower bound of f(n) = 100 n + 50 ❑ if c g(n) n0 - c and n0 are +ve real constants ❑ f(n) = Ω( g(n) ) ❑ c= 5, no= ? Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 03 2 /19  Asymptotic Analysis Theta ϴ (Tight Bound) Durgesh Kumar (VIT Vellore) DSA : BCSE202 L Week 1: Lecture 03 2 /19  Asymptotic Analysis Theta ϴ (Tight Bound) ❑ Given f(n) ❑ Lower Bound ϴ can be written as g(n) ❑ if c1 g(n)