Introduction to Data Structures, Algorithms, and Arrays

Introduction to Data Structures and Algorithms

• Definition of Data: Data refers to raw facts, figures, symbols, or values collected for processing. Data by itself may not provide meaningful information; however, after processing, data becomes information.

• Examples of Data:

  • Student name

  • Roll number

  • Marks

  • Mobile number

  • Salary details

• Data Structure Definition:

  • A method of organizing and storing data in a computer so that it can be accessed and processed efficiently.

  • Alternatively, it is the logical arrangement of data elements along with the relationship between them.

• Need for Data Structures:

  1. Efficient storage of data.

  2. Fast searching and retrieval.

  3. Easy insertion and deletion of data.

  4. Better memory utilization.

  5. Faster processing of information.

  6. Organizing data systematically.

  7. Reducing program complexity.

• Advantages of Data Structures:

  • Efficient Storage: Helps in storing large amounts of data in an organized manner.

  • Fast Access: Data can be accessed and retrieved quickly and easily.

  • Easy Processing: Operations like insertion, deletion, searching, and sorting become easier.

  • Better Memory Utilization: Helps in proper utilization of computer memory and reduces memory wastage.

  • Faster Execution: Programs execute faster and more efficiently using suitable data structures.

Classification of Data Structures

• Primitive Data Structures: These are basic and fundamental data types directly supported by the programming language and computer hardware. They store only a single value.

  • INTEGER (int): Used to store whole numbers without decimal points. Example: int age = 20; printf("%d", age);.

  • CHARACTER (char): Used to store a single character. Example: char grade = 'A'; printf("%c", grade);.

  • FLOAT (float): Used to store decimal numbers with single precision. Example: float mark = 89.5; printf("%f", mark);.

  • DOUBLE (double): Used to store large decimal numbers with double precision. Example: double salary = 45678.9876; printf("%lf", salary);.

• Non-Primitive Data Structures: Complex data structures derived from primitive data types. They are used to store multiple values and relationships between data elements.

  • Linear Data Structures: Elements are arranged sequentially one after another.

    • Array: A collection of similar type of elements stored in consecutive memory locations. Example: int a[5] = {10, 20, 30, 40, 50};.

    • Linked List: A collection of nodes where each node contains data and the address of the next node. Nodes are connected using pointers.

    • Stack: A linear structure where insertion and deletion occur at only one end called the TOP. It follows LIFO ($\text{Last In First Out}$).

    • Queue: A linear structure where insertion is done at the REAR and deletion is done at the FRONT. It follows FIFO ($\text{First In First Out}$).

  • Non-Linear Data Structures: Elements are not arranged sequentially; one element can be connected to multiple elements to represent hierarchical or network relationships.

    • Tree: A hierarchical structure consisting of nodes connected by edges. The topmost node is the ROOT node.

    • Graph: A structure consisting of Vertices (Nodes) and Edges (Connections).

Algorithm Analysis and Mathematical Background

• Algorithm: A finite set of step-by-step instructions or a systematic procedure used to solve a problem or perform a specific task in a finite number of steps.

• Mathematical Background of Analysis: Used to measure and compare efficiency based on execution time, memory usage, and growth rate.

  • Constant Function: $f(n) = 1$. Execution time remains the same for all inputs. Complexity: $O(1)$.

  • Linear Function: $f(n) = n$. Execution time increases directly with input size. Complexity: $O(n)$.

  • Quadratic Function: $f(n) = n^2$. Execution time increases as the square of input size (e.g., nested loops). Complexity: $O(n^2)$.

  • Logarithmic Function: $f(n) = \log(n)$. Execution time increases slowly even for large inputs. Complexity: $O(\log(n))$.

  • Exponential Function: $f(n) = 2^n$. Execution time increases very rapidly. Complexity: $O(2^n)$.

• Order of Growth: O(1) < O(\log(n)) < O(n) < O(n^2) < O(2^n). Speed ratings: $O(1)$ (Very Fast), $O(\log(n))$ (Fast), $O(n)$ (Moderate), $O(n^2)$ (Slow), $O(2^n)$ (Very Slow).

Performance Analysis: Time and Space Complexity

• Performance Analysis: Analyzing the efficiency of a program before execution. Actual execution time is performance measurement.

• Space Complexity: The amount of memory space required by an algorithm to execute completely. Components include:

  • Fixed Part: Independent of input size. Includes program instructions, constants, simple variables, and fixed-size variables.

  • Variable Part: Depends on the problem instance. Includes dynamic variables, referenced variables, and recursion stack space.

  • Representation: $S(P) = c + Sp(\text{Instance Characteristics})$, where $c$ is the fixed part and $Sp$ is the variable part.

  • Constant Space Example: An algorithm returning a math expression like a + b + b * c + (a + b - c) / (a + b) + 4.0 has no recursion or dynamic allocation; thus $Sp = 0$ and it uses constant space.

• Time Complexity: The amount of time required by an algorithm to execute completely. Compile time is ignored; only run time matters.

  • Representation: $tp(n) = ca \times \text{ADD}(n) + cs \times \text{SUB}(n) + cm \times \text{MUL}(n) + cd \times \text{DIV}(n) + \dots$

  • Step Count Method: Assumes each meaningful operation takes one unit of time. $\text{Total Time} = \text{Number of Steps} \times \text{Unit Time}$.

  • Frequency Count Method: Counts how many times each statement is executed.

• Factors Affecting Runtime: Number of comparisons, number of data exchanges, recursive calls, program size, and input data size.

• Comparison:

  • Time Complexity: Measures execution speed; depends on number of operations.

  • Space Complexity: Measures memory usage; depends on memory allocation.

Computational and Asymptotic Complexity Cases

• Best Case Analysis: Minimum time required. Occurs when the desired element is at the first position or minimum operations are performed. Represents the lower bound. Example: Linear search finding the item at index 0.

• Worst Case Analysis: Maximum time required. Occurs when the element is at the last position or not present. Represents the upper bound and is the most common metric. Example: Linear search checking all $N$ elements.

• Average Case Analysis: Average execution time for all possible inputs based on probability. Usually lies between best and worst case.

• Asymptotic Notations:

  • Big O Notation ($O$): Represents the upper bound (worst-case). $f(n) = O(g(n))$ if there exist constants $c$ and $n_0$ such that $f(n) \leq c \times g(n)$ for all $n \geq n_0$. Example: $3n + 2 \leq 4n$ for $n \geq 2$, so $3n + 2 = O(n)$.

  • Omega Notation ($\Omega$): Represents the lower bound (best-case). $f(n) = \Omega(g(n))$ if $f(n) \geq c \times g(n)$ for all $n \geq n_0$. Example: $3n + 2 \geq 3n$, so $3n + 2 = \Omega(n)$.

  • Theta Notation ($\Theta$): Represents the exact behavior (both upper and lower bound). $c_1 \times g(n) \leq f(n) \leq c_2 \times g(n)$ for all $n \geq n_0$.

Arrays: Implementation and Memory Allocation

• Arrays: A collection of homogeneous (same data type) elements stored in contiguous/consecutive memory locations. Access is via an index or subscript (starting at 0 in C).

• One-Dimensional Array Declaration: data_type array_name[size];. Example: int num[5];.

• Size Calculation: $\text{Size} = (UB - LB) + 1$. For int num[5], $LB = 0, UB = 4$, so $\text{Size} = (4 - 0) + 1 = 5$.

• Memory Requirement: $\text{Memory Size} = \text{Number of elements} \times \text{Size of one element}$. Example: float val[10]; ($10 \times 4\,bytes = 40\,bytes$).

• Initialization:

  • int ex[10] = {12, 23, 9, 17, 16, 49}; (Remaining 4 elements become 0).

  • char word[10] = {'h', 'e', 'l', 'l', 'o', '\0'}; or char name[20] = "John Doe";.

• Address Calculation Formula (1D Array): $\text{Address of } A[I] = B + W \times (I - LB)$

  • $B$: Base Address (address of the first element).

  • $W$: Size of one element in bytes.

  • $I$: Index of the target element.

  • $LB$: Lower Bound of the array.

  • Problem Example: Base address = $1020$, $LB = 1300$, element size = $2$. Find address of $A[1700]$. Result: $1020 + 2 \times (1700 - 1300) = 1020 + 800 = 1820$.

• Advantages/Limitations:

  • Advantages: Fast access via index, efficient memory utilization for known sizes, simple implementation.

  • Limitations: Fixed size, homogeneous only, difficult insertions/deletions (requires shifting).

Array Operations and Algorithms

• Traversal: Visiting each element exactly once. Used for displaying elements or performing calculations.

• Insertion: Adding an element at a specified position. Elements after the position must be shifted right.

• Deletion: Removing an element. Subsequent elements must be shifted left to fill the gap.

• Addition/Subtraction/Multiplication: Performed on corresponding elements of two arrays. Algorithm: $\text{Repeat for } i = 0 \text{ to } n-1: C[i] = A[i] \text{ [op] } B[i]$.

• Applications:

  • Sparse Matrix Representation: A matrix where most elements are zero. Stored by only keeping non-zero elements to save space. Types: Lower Triangular (zeros above diagonal), Upper Triangular (zeros below diagonal), and Tridiagonal (non-zeros only on/adjacent to main diagonal).

  • Polynomial Representation: Storing coefficients in an array where the index represents the exponent. Example: $5x^3 + 4x^2 + 2x^1 + 7$ stores [7, 2, 4, 5].

  • Polynomial Addition: Comparing exponents and adding coefficients of the same degree.

Searching Techniques

• Linear Search (Sequential Search):

  • Checks elements one by one from the start.

  • Works on sorted and unsorted arrays.

  • Best Case: $O(1)$ (found at index 0).

  • Worst Case: $O(n)$ (found at last index or not present).

  • Average Case: $O(n)$.

• Binary Search:

  • Used only for sorted arrays. Follows Divide and Conquer.

  • Repeatedly divides the search space in half using mid = (beg + end) / 2.

  • Best Case: $O(1)$.

  • Worst/Average Case: $O(\log(n))$.

  • Space Complexity: $O(1)$.

Sorting Techniques

• Selection Sort:

  • Repeatedly finds the minimum element from the unsorted part and swaps it with the first unsorted element.

  • Time Complexity: $O(n^2)$ for all cases (Best, Average, Worst).

  • Space Complexity: $O(1)$.

  • Performs fewer swaps than bubble sort.

• Bubble Sort:

  • Compares adjacent elements and swaps them if they are in the wrong order. Larger elements "bubble" to the end.

  • Optimized Bubble Sort: Uses a flag to stop if no swaps occur in a pass.

  • Worst/Average Case: $O(n^2)$.

  • Best Case (Optimized): $O(n)$.

• Insertion Sort:

  • Virtually splits the array into sorted and unsorted parts. Inserts the next unsorted element into its proper place in the sorted part.

  • Worst/Average Case: $O(n^2)$.

  • Best Case: $O(n)$ (already sorted, only comparisons).

  • Efficient for small/partially sorted data.

• Quick Sort:

  • Divide and Conquer algorithm. Selects a pivot and partitions the array into elements smaller than the pivot (left) and larger than the pivot (right).

  • Partitioning: Rearranges elements around the pivot; the pivot reaches its final sorted position.

  • Best/Average Case: $O(n \log(n))$.

  • Worst Case: $O(n^2)$ (occurs if the array is already sorted or reverse-sorted).

  • Space Complexity: $O(\log(n))$ due to recursion stack.