IMG_7444.jpeg

# Data Structures and Algorithms ## Algorithms ### Definition An algorithm is a step-by-step procedure to solve a problem. ### Properties * **Finiteness**: An algorithm must always terminate after a finite number of steps. * **Definiteness**: Each step must be precisely stated. * **Input*...

# Data Structures and Algorithms ## Algorithms ### Definition An algorithm is a step-by-step procedure to solve a problem. ### Properties * **Finiteness**: An algorithm must always terminate after a finite number of steps. * **Definiteness**: Each step must be precisely stated. * **Input**: An algorithm accepts zero or more inputs. * **Output**: An algorithm produces one or more outputs. * **Effectiveness**: Each step must be basic enough to be carried out. ### Factors * **Time Complexity**: Time required by an algorithm. * **Space Complexity**: Space required by an algorithm. ## Data Structures ### Definition A data structure is a way of organizing and storing data in a computer so that it can be used efficiently. ### Types * **Primitive Data Structures**: Integer, Float, Character, String, etc. * **Non-Primitive Data Structures**: * **Linear Data Structures**: Array, Linked List, Stack, Queue * **Non-Linear Data Structures**: Tree, Graph ### Array * Collection of similar data elements. * Elements are accessed using an index. * Types: * One Dimensional Array * Two Dimensional Array * Multi-Dimensional Array ### Linked List * Collection of nodes. * Each node contains data and a pointer to the next node. * Types: * Singly Linked List * Doubly Linked List * Circular Linked List ### Stack * Follows LIFO (Last In First Out) principle. * Operations: * Push (insert) * Pop (remove) * Applications: * Expression evaluation * Function calls ### Queue * Follows FIFO (First In First Out) principle. * Operations: * Enqueue (insert) * Dequeue (remove) * Types: * Simple Queue * Circular Queue * Priority Queue ### Tree * Hierarchical data structure. * Consists of nodes and edges. * Types: * Binary Tree * Binary Search Tree (BST) * AVL Tree * B-Tree ### Graph * Collection of vertices and edges. * Types: * Directed Graph * Undirected Graph * Representations: * Adjacency Matrix * Adjacency List ## Common Algorithms ### Searching Algorithms * **Linear Search**: Sequentially checks each element in the list until a match is found or the whole list has been searched. * Time Complexity: $O(n)$ * **Binary Search**: Searches a sorted array by repeatedly dividing the search interval in half. * Time Complexity: $O(log n)$ ### Sorting Algorithms * **Bubble Sort**: Repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. * Time Complexity: $O(n^2)$ * **Insertion Sort**: Builds the final sorted array one item at a time. * Time Complexity: $O(n^2)$ * **Selection Sort**: Repeatedly finds the minimum element from unsorted part and puts it at the beginning. * Time Complexity: $O(n^2)$ * **Merge Sort**: Divides the unsorted list into $n$ sublists, each containing one element; repeatedly merges sublists to produce new sorted sublists; and finally merges the two sublists to produce a single sorted list. * Time Complexity: $O(n log n)$ * **Quick Sort**: Picks an element as pivot and partitions the given array around the picked pivot. * Time Complexity: $O(n log n)$ (average), $O(n^2)$ (worst) * **Heap Sort**: Heap sort is a comparison based sorting technique based on Binary Heap data structure. * Time Complexity: $O(n log n)$ ## Complexity Analysis ### Time Complexity * **Big O Notation**: Describes the worst-case scenario. * $O(1)$: Constant * $O(log n)$: Logarithmic * $O(n)$: Linear * $O(n log n)$: Linearithmic * $O(n^2)$: Quadratic * $O(2^n)$: Exponential * $O(n!)$: Factorial ### Space Complexity * Amount of memory space required by the algorithm to execute. * Includes space for input values and auxiliary space.