Scribd Logo
Upload

Welcome to Scribd!

  • 276 views

    Analysis and Design of Algorithms

    Uploaded by

    Shivani Srivastava
    This document discusses algorithms and their analysis. It covers topics like common algorithm analysis books, the definition of an algorithm, complexity analysis using asymptotic notations like Big O, and an example pseudocode for finding the deviation from the average. It also briefly discusses algorithm design techniques, complexity classes, and how the choice of algorithm affects performance on different systems.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd

    Analysis and Design of Algorithms

    Uploaded by

    Shivani Srivastava
    276 views15 pages
    This document discusses algorithms and their analysis. It covers topics like common algorithm analysis books, the definition of an algorithm, complexity analysis using asymptotic notations like Big O, and an example pseudocode for finding the deviation from the average. It also briefly discusses algorithm design techniques, complexity classes, and how the choice of algorithm affects performance on different systems.

    Original Title

    1 Analysis+and+Design+of+Algorithms

    Copyright

    © © All Rights Reserved

    Available Formats

    PPT, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document discusses algorithms and their analysis. It covers topics like common algorithm analysis books, the definition of an algorithm, complexity analysis using asymptotic notations like Big O, and an example pseudocode for finding the deviation from the average. It also briefly discusses algorithm design techniques, complexity classes, and how the choice of algorithm affects performance on different systems.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    276 views15 pages

    Analysis and Design of Algorithms

    Uploaded by

    Shivani Srivastava
    This document discusses algorithms and their analysis. It covers topics like common algorithm analysis books, the definition of an algorithm, complexity analysis using asymptotic notations like Big O, and an example pseudocode for finding the deviation from the average. It also briefly discusses algorithm design techniques, complexity classes, and how the choice of algorithm affects performance on different systems.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    of 15

    Analysis and Design of

    algorithms

    1
    Books
     Fundamentals of Computer algorithms
    Horowitz, Sahani and Rajasekaran

     Introduction to Algorithms
    Coremen, Leiserson

     The Design and Analysis of Computer


    Algorithms
    Aho, Hopcroft and Ullman
    2
    ALGORITHM

    A finite set of instructions which if


    followed accomplish a particular task.
    In addition every algorithm must satisfy
    following criteria:

    3
    1. Input: zero or more quantities externally
    supplied
    2. Output: at least one quantity is produced
    3. Definiteness: Each instruction must be
    clear and unambiguous.
    4. Finiteness: In all cases algorithm must
    terminate after finite number
    of steps.
    5. Effectiveness: each instruction must be
    sufficiently basic.
    4
    • Two algorithms on two systems
    • Algorithm A1 50 n lg n
    • Algorithm A2 2 n2

    A2 Super computer
    108 ins/sec

    A1
    P.C
    106 ins /sec

    5
    For n = 106

    Time taken by Super Computer


    = 2.(106)2/ 108 = 20,000 sec

    Time taken by P .C.


    = 50 . 106 lg 106 / 106 = 1,000 sec

    6
    Thus by using a fast algorithm , the personal
    computer gives results
    20 times faster than the result given by
    super computer using a slow algorithm.

    Thus a good algorithm is like a sharp knife,


    it does exactly what it is supposed to do
    with a minimum amount of effort.

    7
    Complexity
    Some questions to answer:
     How fast can we solve a
    problem?
     There may be many algorithms for a
    given problem. Which algorithm to use?
     What are the classical algorithm
    design techniques ?
     Are there problems inherently difficult
    to solve?
    8
    How do we express the complexity of algorithm?

    Resources : Time and Space

    Complexity lower bounds for problems.

    Complexity classes P, NP etc.

    9
    Pseudocode
    • Pseudocode is an English language like
    representation of the code required for an algorithm.

    • It is partly English, partly structured code.

    • The English part provides a relaxed syntax that is


    easy to read.

    • The code part consists of an extended version of the


    basic algorithmic constructs-sequence, selection and
    iteration.
    10
    Sequence, selection, loop
    • A sequence is a series of statements that do not
    alter the execution path within an algorithm.
    • Statements such as assign and add are
    sequence statements.
    • A call to another algorithm is also considered a
    sequence statement.
    • Selection statements evaluate one or more
    alternatives. Paths are followed based on its
    result.

    11
    • The typical selection statement is the two
    way selection
    • if (condition) action 1 else action 2.
    • The part of the loop are identified by
    indentation.
    • Loop iterates a block of code. It closely
    resembles the while loop. It is a pretest
    loop.

    12
    Example
    Algorithm deviation
    It finds deviations from average.

    Pre: nothing
    Post: numbers are read and deviation
    from average printed

    13
    1 i= 0
    2 Loop(all data are read)
    1 I=I+1
    2 read numbers into array[i]
    3 sum = sum + number
    3 Average = sum / I
    4 Print (average)
    5 J=0
    6 Loop (j < i)
    1 j = j+ 1
    2 dev = array[j] – average
    3 print (array [ j] . Dev)
    7 Return
    8 End deviation

    14
    Asymptotic notations( O , Ω , Θ )

    15

    You might also like