Scribd Logo
Upload

Welcome to Scribd!

  • 7K views

    Design and Analysis of Algorithms S. Sridhar

    Uploaded by

    Teena Alugula

    Copyright:

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

    Design and Analysis of Algorithms S. Sridhar

    Uploaded by

    Teena Alugula
    7K views31 pages

    Original Title

    1_Design_and_Analysis_of_Algorithms-Ch-1.pptx

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    7K views31 pages

    Design and Analysis of Algorithms S. Sridhar

    Uploaded by

    Teena Alugula

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    You are on page 1of 31

    Design and Analysis

    of Algorithms

    S. Sridhar
    Chapter 1

    Introduction to Algorithms

    © Oxford University Press 2014. All rights reserved.


    Chapter Objectives

    © Oxford University Press 2014. All rights reserved.


    What is an algorithm?
    • An algorithm is a set of instructions to solve a given problem.

    © Oxford University Press 2014. All rights reserved.


    Some Examples of Algorithms in daily life

    © Oxford University Press 2014. All rights reserved.


    A Typical Algorithm Environment

    © Oxford University Press 2014. All rights reserved.


    Characteristics of an Algorithm

    © Oxford University Press 2014. All rights reserved.


    Characteristics of an Algorithm

    © Oxford University Press 2014. All rights reserved.


    Need for Efficiency

    • Time

    • Space

    © Oxford University Press 2014. All rights reserved.


    Stages of Problem Solving
    • Understanding the problem
    • Planning an algorithm
    • Designing an algorithm
    • Validating and verifying an algorithm
    • Analyzing an algorithm
    • Implementing an algorithm
    • Performing empirical analysis (if necessary)

    © Oxford University Press 2014. All rights reserved.


    Computation Model
    Need of Computation model

    © Oxford University Press 2014. All rights reserved.


    Data Organization

    © Oxford University Press 2014. All rights reserved.


    Algorithm Design

    © Oxford University Press 2014. All rights reserved.


    Algorithm Specification
    Communication to programmer is called algorithm
    specification
    1. Natural Language
    2. Pseudocode
    3. Programming language

    © Oxford University Press 2014. All rights reserved.


    Validating and Verification

    © Oxford University Press 2014. All rights reserved.


    Analysis of Algorithms

    © Oxford University Press 2014. All rights reserved.


    Time and Space Complexity

    © Oxford University Press 2014. All rights reserved.


    Comparison of Algorithms

    © Oxford University Press 2014. All rights reserved.


    Empirical and Post martem Analysis

    © Oxford University Press 2014. All rights reserved.


    Classification of Algorithms

    © Oxford University Press 2014. All rights reserved.


    Recursive Algorithms

    © Oxford University Press 2014. All rights reserved.


    Parallel and Distributed Algorithms

    © Oxford University Press 2014. All rights reserved.


    Exact Vs Approximation Algorithms

    © Oxford University Press 2014. All rights reserved.


    Deterministic Vs randomized Algorithms

    © Oxford University Press 2014. All rights reserved.


    Based on Design

    Example Greedy, dynamic programming, Brute force


    Techniques.

    © Oxford University Press 2014. All rights reserved.


    Based on Specialization
     General Algorithms
     Example; Searching and Sorting
     Domain Specific Algorithms
     String Algorithms
     Graph Algorithms

    © Oxford University Press 2014. All rights reserved.


    Some Interesting Problems

    © Oxford University Press 2014. All rights reserved.


    Based on Tractability

    © Oxford University Press 2014. All rights reserved.


    Example of Tractability

    © Oxford University Press 2014. All rights reserved.


    Glossary

    © Oxford University Press 2014. All rights reserved.


    Glossary

    © Oxford University Press 2014. All rights reserved.

    You might also like