DAA

• Algorithm


  A well-defined computational procedure that takes some value or a set of values as input and produces some value or a set of values as output

  
• Algorithm


  • It is a step-by-step procedure for solving a problem in a finite amount of time
  • Algorithms are the dynamic part of a program's world model
  • Algorithms are not dependent on a particular programming language, machine, system, or compiler
• Data structure


  The structural representation of logical relationship between elements of data
• Abstraction


  The process of classifying characteristics as relevant and irrelevant for the particular purpose at hand and ignoring the irrelevant ones
• Abstract Data Type (ADT)


  An abstraction of a data structure that specifies what can be stored and what operations can be done on/by the ADT
• Classification of Data Structures


  • Linear
  • Non-linear

  
• Complexity Analysis


  An objective way to evaluate the cost of an algorithm or code section in terms of space or time
• Mathematical Analysis of Algorithms

  1. Decide on a parameter(s) for the input, n

  2. Identify the basic operation

  3. Evaluate if the elementary operation depends only on n

  4. Set up a summation corresponding to the number of elementary operations

  5. Simplify the equation to get as simple of a function T(n) as possible

  
• Performance Analysis


  The process of predicting the resources which are required for an algorithm to perform its task
• Performance Analysis


  • Compares algorithms solving the same problem to select the best one
  • Considers space and time required by the algorithm
• Space Complexity


  The total amount of memory required by an algorithm to complete its execution
• Space complexity includes program space, data space, and other requirements like function calls and jumping statements
• When we want to analyze an algorithm, we consider only the space and time required by that particular algorithm and we ignore all the remaining elements.
• Performance analysis of an algorithm

  The process of calculating space and time required by that algorithm
• Measures used in performance analysis of an algorithm

  • Space required to complete the task of that algorithm (Space Complexity)
  • Time required to complete the task of that algorithm (Time Complexity)
• Space complexity


  The total amount of computer memory required by an algorithm to complete its execution
• Purposes for which memory is required by an algorithm


  • To store program instructions
  • To store constant values
  • To store variable values
  • For function calls, jumping statements etc.
• Time complexity


  The total amount of time required by an algorithm to complete its execution
• Factors that affect the running time of an algorithm

  • Whether it is running on Single processor machine or Multi processor machine
  • Whether it is a 32 bit machine or 64 bit machine
  • Read and Write speed of the machine
  • The amount of time required by the algorithm to perform Arithmetic operations, logical operations, return value and assignment operations etc.
  • Input data
• Algorithm analysis requires a set of rules to determine how operations are to be counted.
• Rules for algorithm analysis


  • Assume an arbitrary time unit
  • Execution of certain operations takes time 1
  • Running time of a selection statement is the time for the condition evaluation plus the maximum of the running times for the individual clauses
  • Loop execution time is the sum, over the number of times the loop is executed, of the body time plus time for the loop check and update operations, plus time for the loop setup
  • Running time of a function call is 1 for setup plus the time for any parameter calculations plus the time required for the execution of the function body
• When we calculate time complexity of an algorithm, we consider only input data and ignore the remaining things, as they are machine dependent.
• Kinds of analysis


  • Worst case
  • Best case
  • Average case
• Worst case


  Provides an upper bound on running time, an absolute guarantee that the algorithm would not run longer, no matter what the inputs are
• Best case


  Provides a lower bound on running time, the input is the one for which the algorithm runs the fastest
• Average case


  Provides a prediction about the running time, assumes that the input is random
• Order of growth is how the time of execution depends on the length of the input. Whenever we want to perform analysis of an algorithm, we need to calculate the complexity of that algorithm.
• Instead of taking the exact amount of resource, we represent that complexity in a general form (Notation) which produces the basic nature of that algorithm.
• Asymptotic notations


  • O
  • W
  • Q
  • o
  • w
• 1. notation


  Represents an asymptotic upper bound for a function
• 1. notation


  Represents an asymptotic lower bound for a function
• 1. notation


  Represents an asymptotically tight bound for a function
• Q(g(n)) = O(g(n)) ∩ W(g(n))
• f(n) = Q(g(n)) iff f(n) = O(g(n)) and f(n) = W(g(n))
• Properties of asymptotic notation


  • Transitivity
  • Reflexivity
  • Symmetry
  • Complementarity
• Exponentials and polynomials: lim(n->∞) (a^n/n^m) = 0 for any positive integers m and n
• Logarithms: lg2a = (lg a)^2, lg lg a = lg (lg a)