INTRODUCTION TO DSA ©_WHATIS DATA STRUCTURE: | a © Collection of data elements organized in a structured way. = Examples: Arrays, Linked Lists, Stacks, Queues, Trees © WHAT IS ALGORITHM: © Step-by-step procedure or formula for solving a problem. Examples: Searching, Sorting, Calculating © WHY DSA IS IMPORTANT: | © Improves problem-solving skills © Write efficient & optimized code © Helps in coding interviews & contests © Used in various applications & fields © APPLICATIONS 6F DSA | (© Search Engines: Search & ranking results © Social Media: News feeds, friend suggestions © E-Commerce: Recommendation systems ‘© Navigation: Maps & routes optimization (© Cybersecurity: Encrypting & decrypting data © Managing a to-do list (stack operations) ‘© Rescheduling jobs (priority queue) © Finding the best route (graph algorithms)TYPES OF DATA STRUCTURES (Page 2) © PRIMITIVE DATA STRUCTURES’ © Basic structures built-in to a programmining language. =o Integers (int) —© Floats (float) =o Characters (char) —0 Booleans (bool) © NON-PRIMITIVE DATA STRUCTURES: | © Derived from primitive data structures, used to store data > Linear vs Non-Linear (hierarchical) © STATIC vs NON-LINEAR: | ‘© Linear Data Structures: Interest from tronpdents © Non-Linear Data Structures: Inverst-trom complimorities © STATIC vs DYNAMIC: | OSTATIC: Fixed size, defined at compile-time © DYNAMIC: Size can change during runtime. © KEY POINTS: | © Primitive are basic; Non-Primitive are derived © Linear are sequential; Non-Linear are hierarchical © Static are fixed-size; Dynamic can grow/shrink @mastercode-sagarTIME & SPACE COMPLEXITY ee © Refers to the amount of time an algorithm takes to run as input size grows © Helps identify the efficiency and performance of an algorithm, b Example: Sorting an array Se O(n?) © SPACE COMPLEXITY: | (© Refers to the amount of memory an algorithm requires © Helps understand the memory usage of an algorithm. > Example: Creating a new array => O(n) © WHY COMPLEXITY MATTERS: © Helps write optimized & efficient code © Allows to compare different algorithms © Ensures good performance for large data sets © BEST, AVERAGE, WORST CASE: © Best Case: Minimum time/space, oxecple © Average Case: Typical time/space, commony © Worst Case: Maximum time/space, lest efficient scenario © KEY PONTE: & V Time Complexity: Efficiency ofan algorithm © '3, 7, !, 4,4) VY Space Complexity: Memory usage of an algorithm Y Consider best, average & worst case for analysing an algorithm @Mastercode sagorASYMPTOTIC NOTATIONS (Page 4) _BIG-O NOTATION: | © Represents the upper bound of an algorithm. Worse Case (How bad can it be?") Timea] » Denoted as O(F(n)) Eager > Example: O(n?), O(n log n) et Se © BiG-Q (OMEGA) NOTATION: | © Represents the lower bound of an algorithm. 4 [SGn) & Best Case (‘How good can it be") Time n] > Denoted as Q¢F(n)) 2) » Example: Q(n), Q(log n) a Input Size (7) _BIG-© (THETA): | © Represents the tight (precise) bound of an algorithm. > Average Case (What's the tight bound?) Tine () p Denoted as O(F(n)) == Example: @(n?), @(n logn) Input Size) ¥ Big-O: Upper bound of an algorithm ¥ Big-Q: Lower bound of an algorithm Y Big-©: Tight bound & precise V Understand the difference to analyze algorithms @[Link]ARRAYS (Page 5) © WHAT IS ARRAY: | © Simple data structure that stores elements of the same type at contiguous memory locations © Example: int arr{s] = (10, 20, 30, 40,50); | ENBESORARRASS: | © One-Dimensional Array (1D): | © Linear list of elements | (© Two-Dimensional Array (2D): > Matrix-like structure © Multi-Dimensional Array: © Arrays within arrays (3D, 4D, ...) © ADVANTAGES: | © Fast access to elements using index © Eosy traversal using loops (iteration) © Useful for storing similar data types © DISADVANTAGES: | © Fixed size (static) © Insertion & deletion is costly © Inefficient memory usage in case of sparse arrays ©. MEMORY REPRESENTATION: © Arrays use contiguous memory locations ~» Base Address: 1000 -> Site: -> Formula: Address = Base Address + (Index x SizeOf (DataType) KEY POINTS: | v Arrays store similar type elements at contiguous locations Fost access using index: Weakness: fixed size, costly operations ¥ One-dimensional, 2D, ond Multi dimensional orrays available @[Link]SEARCHING ALGORITHMS (Page 6) © Searching Algorithms are used to find the location of an element in a data OEINSRYASEARGH: | © Searches for an element © Searches for an element by repeatedly sequentially in a list until dividing the sorted list in half is found > Example: Target: 9 > Ons) BIBeNpe jae S1 ae ae (SPT Te ls ar -teroet: 9 © Time Complexity: O(n) © Time Complexity: O(log n) [PRS eens SSS Vv Simple & easy | »Slow for | |v Fast ondeffiert | v Works only on sorted to implement large tists | | (Oleg) data Werks en unsorted| » Inefficient| | v Great for lorge | ¥ Requires additional | dota Cm) sertedilists | logic ! © | SEARCHING ALGORITHMS: | 100 l= | SS eRee ees Target: 97 NS V Fast and efficient (O(log »)) V Great for large sorted lists |v Simple & easy to implement |v Werks on unsorted data © KEY POINTS: V Linear Search: Sequential, Simple, Works on unsorted data, O(n) ¥ Binary Search: Efficient, Sorted lists, Uses divide & conquer, O(log n) V Choose based on data type and size for better performance © KEY POINTS: | Y Linear Search: Sequential, Simple, Works on unsorted data, O(n) Y Binary Search: Efficient, Sorted lists, Uses divide & conquer, O(log n) @mostercode sagarwee a a a fal SORTING BASICS (Page 7) © WHAT IS SORTING: © Sorting means arranging the elements of a list in a specific order (ascending or descending) > Example: Before: [12, 5, 3, 1] voter fll sls [ra] © WHY SORTING? © Makes searching, indexing, and merging more efficient © Organizes data for better comprehension O TYPES OF SORTING ALGORITHMS: © Repeatedly swaps adjocent —_ 0 Repeatedly selects the minimum eeeenre element *(2 PRB hs) + Geils!) * Time Complexity: O(n?) % Time Complexity: O(n?) [Merge Sort | [Quick Sort | © Divides the list into-haives, | 0 Selects a pivot, partitoms around! tt eae » is leger] * (STsTi[2[s]4[e] a > te corrtenty ong) |” (2-18 lek sle MERE % Time Complexity: OC{[Link]) Y Sorting arranges elements in a specific order (asc/desc) y V Helps in efficient searching, merging, ete. V Bubble & Selection: Simple; Merge & Quick: Efficient. @[Link]SORTING ALGORITHMS (Page 8) © Repeatedly swaps adjacent elements | [S[3]3]alal2h[1]2]2 & Simple but slow See ~> Example: (5518.12 | GiieisisPolsis | — = Time Complexity: O(n?) = Time Complexity: O(n?) © SELECTION SORT: © Repeatedly selects the minimum element > Simple but inefficient: © Repeatedly swaps adjacent © Repeatedly selects the minimum element. elements > Simple but slow => Time Complexity: O(n") > Simple but inefficient >S23 24S hbEEEIs0 > Time Complexity: O(n*) / O(n log n) (© Uses divide and conquer approach © Selects a pivot to partiton the list © Efficient for large lists © Very fast in practice sBisléhisebBe) (ise 2I7>GBRiisle > Time Complexity: O(n?) —> Time Complexity: O(n?) © KEY POINTS: | V Bubble Sort & Selection Sort: Simple, O(n?) V Merge Sort: Efficient, Divide & Conquer, O(n logn) V Quick Sort: Highly Efficient, Prot bosed, O(n?) / O(nlog n) © | KEVIFOINTS:) V Bubble Sort & Selection Sort: Simple, O(n?) V Merge Sort: Efficient, Divide & Conquer, O(nlegn) VY Quick Sort: Highly Efficient, Prot bosed, O(n?) / O(nlogn) @estercodesogorSELECTION SORT (Page Sa © Select the minimum element and place it at the correct position © Find the smallest element and move it to the beginning. © ALGORITHM STEPS: © Start from the first position © Find the minimum element in the list © Swap the min element with the first position © Repeat the process for the rest of the list 2 | :swap | (J 4 miunnunt element) ‘owop = (ETURIER ISTE] sswop | [2D273 [514 swap) [pais se J:swopl (2 TS 1415: o Best: O(n?) © O11) © Average: O(n?) | © Worst: O(n?) v KEY POINTS: | + In-place sorting ¥ Not stable (by default) @[Link]