Unit-1 ADA notes

on
https://drive.google.com/file/d/1RFeCY_Kpc5dr9gTj1QOIiIuaSiNyeXg_/view?usp=sharing








The document provides a detailed summary of algorithms, including their definition, specification, performance analysis, and various design techniques like Divide and Conquer, with specific examples such as Binary Search, Merge Sort, and Quick Sort.

1. Algorithm Fundamentals
  • Definition and Criteria: An algorithm is defined as a finite sequence of instructions, each with a clear meaning, that terminates after a finite number of steps. Every algorithm must satisfy the following criteria: Input (zero or more externally supplied quantities), Output (at least one produced quantity), Definiteness (clear and unambiguous instructions), Finiteness (terminates after a finite number of steps for all cases), and Effectiveness (basic and feasible instructions).
  • Algorithm Specification: Algorithms can be described in three ways:
    • Natural language like English, ensuring each statement is definite.
    • Graphic representation called a flowchart, which works well for small and simple algorithms.
    • Pseudo-code method, which describes algorithms as programs resembling languages like Pascal and Algol.
  • Pseudo-Code Conventions: Conventions include starting comments with //, indicating blocks with { and }, and not explicitly declaring variable data types. It uses := for assignment, and logical operators (AND, OR, NOT) and relational operators (<, <=, >, >=, =, !=). Looping statements include For, while, and repeat-until. Conditional statements use If-then and If-then-else forms. Input and output are done using read and write instructions.
  • Algorithm Example (Max): An example algorithm, Algorithm Max(A,n), is provided to find and return the maximum of 'n' given numbers in an array 'A'.
2. Performance Analysis
  • Performance: The performance of a program is the amount of computer memory and time required to run it. Performance analysis uses analytical methods, while performance measurement involves experiments.
  • Time Complexity: The time needed by an algorithm, expressed as a function of the problem size, is the time complexity. The limiting behavior of the complexity as size increases is called the asymptotic time complexity, which determines the size of problems that can be solved.
    • Factors affecting running time include the input, the quality of code generated by the compiler, the nature and speed of the machine's instructions, and the time complexity of the underlying algorithm.
    • The complexity function $f(n)$ depends on the size $n$ and the particular data. Cases include:
      • Best Case: The minimum possible value of $f(n)$.
      • Average Case: The expected value of $f(n)$.
      • Worst Case: The maximum value of $f(n)$ for any possible input.
  • Space Complexity: The amount of memory a program needs to run to completion is its space complexity. It has three components:
    • Instruction space: Space to store the compiled program instructions.
    • Data space: Space to store constants, variable values, and dynamically allocated objects.
    • Environment stack space: Space to save information needed to resume partially completed functions.
    • The space requirement $S(P)$ of an algorithm $P$ is $S(P)=c+S_p(I)$, where $c$ is a constant.
  • Asymptotic Notations: Notations used to characterize algorithm complexity:
    • Big-OH ($O$): Upper Bound; $f(n) = O(g(n))$ means the growth rate of $f(n)$ is less than or equal to that of $g(n)$.
    • Big-OMEGA ($\Omega$): Lower Bound; $f(n) = \Omega(g(n))$ means the growth rate of $f(n)$ is greater than or equal to that of $g(n)$.
    • Big-THETA ($\Theta$): Same order; $f(n) = \Theta(g(n))$ means the growth rate of $f(n)$ equals that of $g(n)$.
    • Little-OH ($o$): $f(n) = o(g(n))$ means $f(n)$ becomes insignificant relative to $g(n)$ as $n$ approaches infinity.
  • Common Computing Times: Common time complexities include $O(1)$, $O(\log_2 n)$, $O(n)$, $O(n \cdot \log_2 n)$, $O(n^2)$, $O(n^3)$, $O(2^n)$, $n!$, and $n^n$.
3. Divide and Conquer Technique
  • General Method: Divide and Conquer is a design strategy that often leads to a large improvement in time complexity, for example, from $O(n^2)$ to $O(n \log n)$ for sorting. The strategy involves three steps:
    1. Divide: Divide the problem instance into two or more smaller instances of the same problem.
    2. Conquer: Solve the smaller instances recursively. The recursion stops when an instance is too small to divide.
    3. Combine: Assemble the solutions to form a solution for the original instance (patching together the answers).
  • Control Abstraction DANDC(P): The time complexity $T(n)$ for a problem of size $n$, assuming the two sub-problems are approximately equal in size, is given by $T(n) = 2T(n/2) + f(n)$ for $n$ not small, where $f(n)$ is the time for Divide and Combine.
4. Specific Algorithms using Divide and Conquer
  • Binary Search (BinSrch):
    • Used to find an element 'x' in an ordered array $x_1 < x_2 < ... < x_n$.
    • It repeatedly jumps into the middle of the un-searched portion of the file, comparing 'x' with $a[mid]$, eliminating roughly half the un-searched portion with each unsuccessful comparison.
    • The worst-case complexity is about $\log_2 n$.
    • The time complexity for a successful search is $O(\log n)$ (Worst Case $\Theta(\log n)$, Average Case $\Theta(\log n)$, Best Case $\Theta(1)$).
    • The time complexity for an unsuccessful search is $\Theta(\log n)$ (best, average, and worst).
    • The worst-case time complexity $w(n)$ for $n=2^k-1$ is $w(n) = \log_2(n+1) = O(\log n)$.
  • Merge Sort (MERGESORT):
    • A classic example of divide and conquer.
    • It recursively sorts the left and right halves of an array separately and then merges them.
    • The fundamental operation is merging two sorted lists, which requires linear extra memory.
    • The time complexity in the best case, worst case, and average case is $O(n \log n)$.
    • The recurrence relation for time complexity, assuming $n=2^k$, is $T(n)=2T(n/2)+n$, which solves to $T(n) = O(n \log n)$.
  • Strassen's Matrix Multiplication:
    • A dramatic example of divide and conquer for multiplying two $n \times n$ matrices.
    • The standard algorithm requires $n^3$ scalar multiplications, leading to $T(n) = O(n^3)$.
    • Strassen's algorithm requires only seven $(n/2) \times (n/2)$ matrix multiplications and eighteen $(n/2) \times (n/2)$ matrix additions/subtractions.
    • The recurrence relation for the number of scalar multiplications is $T(n) = 7T(n/2)$, which solves to $T(n) = O(n^{\log_2 7}) = O(n^{2.81})$, making it asymptotically more efficient than the standard algorithm.
  • Quick Sort (QuickSort):
    • Improves the $O(n^2)$ behavior of simple insertion sort (SIS) with an expected performance of $O(n \log n)$.
    • It partitions the array by rearranging it into two groups: elements less than a chosen pivot element and elements greater than or equal to the pivot.
    • The same partitioning is recursively applied to the two subsets.
    • The Partition() function uses two pointers 'i' and 'j' to find the pivot's proper position.
    • The running time is given by the recurrence relation $T(n)=T(i)+T(n-i-1)+C \cdot n$, where $i$ is the number of elements in the first subset $S_1$.
    • Worst Case Analysis: Occurs when the pivot is the smallest element all the time (i=0), leading to $T(n) = T(n-1) + C \cdot n$, which solves to $O(n^2)$.
    • Average Case Analysis: The average case complexity is $T(n) = O(n \log n)$.





Comments

Post a Comment