Scribd Logo
Upload

Welcome to Scribd!

  • 31 views

    Overview of Algorithm Design

    Uploaded by

    Saraah Ghori
    This document provides an overview of algorithm design and a process for beginners to learn algorithm design. It discusses problem specification, algorithm features, an overall solution strategy, and designing algorithms and data structures together. Key aspects of the design process include specifying inputs, outputs and constraints unambiguously, modeling the problem, developing an initial solution, exploring the solution space, analyzing complexity, finalizing an option, and structuring necessary data. The document demonstrates this process with examples like finding largest/smallest numbers, sorting, Fibonacci numbers, shortest paths, spanning trees, subset sum problems, and the travelling salesperson problem. It also covers time/space complexity, hard problems, approximation, and randomization.

    Copyright:

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

    Overview of Algorithm Design

    Uploaded by

    Saraah Ghori
    31 views9 pages
    This document provides an overview of algorithm design and a process for beginners to learn algorithm design. It discusses problem specification, algorithm features, an overall solution strategy, and designing algorithms and data structures together. Key aspects of the design process include specifying inputs, outputs and constraints unambiguously, modeling the problem, developing an initial solution, exploring the solution space, analyzing complexity, finalizing an option, and structuring necessary data. The document demonstrates this process with examples like finding largest/smallest numbers, sorting, Fibonacci numbers, shortest paths, spanning trees, subset sum problems, and the travelling salesperson problem. It also covers time/space complexity, hard problems, approximation, and randomization.

    Original Description:

    ALgorithm Design

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document provides an overview of algorithm design and a process for beginners to learn algorithm design. It discusses problem specification, algorithm features, an overall solution strategy, and designing algorithms and data structures together. Key aspects of the design process include specifying inputs, outputs and constraints unambiguously, modeling the problem, developing an initial solution, exploring the solution space, analyzing complexity, finalizing an option, and structuring necessary data. The document demonstrates this process with examples like finding largest/smallest numbers, sorting, Fibonacci numbers, shortest paths, spanning trees, subset sum problems, and the travelling salesperson problem. It also covers time/space complexity, hard problems, approximation, and randomization.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    31 views9 pages

    Overview of Algorithm Design

    Uploaded by

    Saraah Ghori
    This document provides an overview of algorithm design and a process for beginners to learn algorithm design. It discusses problem specification, algorithm features, an overall solution strategy, and designing algorithms and data structures together. Key aspects of the design process include specifying inputs, outputs and constraints unambiguously, modeling the problem, developing an initial solution, exploring the solution space, analyzing complexity, finalizing an option, and structuring necessary data. The document demonstrates this process with examples like finding largest/smallest numbers, sorting, Fibonacci numbers, shortest paths, spanning trees, subset sum problems, and the travelling salesperson problem. It also covers time/space complexity, hard problems, approximation, and randomization.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    of 9

    Overview of

    Algorithm Design
    Partha P Chakrabarti
    Department of CSE, IIT Kharagpur
    T10KT Main Workshop
    May 25, 2015

    Developing a Process for a


    Beginner to Learn Algorithm Design
    Problem Specification
    Input, Output, Constraints

    Algorithm Features
    Termination, Functional Correctness, Efficiency,
    User Interface / Interaction, Implementation,
    Error Handling, Documentation

    An Overall Solution Strategy


    Initial Solution, Design Space Exploration and
    Analysis, Algorithm Finalization, Data
    Structuring

    Design, Analysis: Algorithm + Data


    Structure

    Problem Specification
    Unambiguously specify the INPUTS, OUTPUTS,
    CONDITIONS / CONSTRAINTS.
    Make use of logical operations and
    mathematical symbols to the extent possible.
    Additionally give examples to explain the
    specification given where special cases are
    properly highlighted)

    Finding the smallest of n integers.


    Sorting a set of integers.
    Finding the median of a set of numbers.
    Finding the number of matches of a pattern
    in a string.

    Modelling Problem
    Specification
    Modelling, Input, Output, Constraints to
    structures
    Use of Real-Life like Examples
    Finding a route in a map
    Crypt-arithmetic Problem
    Telephone Line Connection Problem
    Time Table Scheduling
    Stamp Selection Problem
    Pumping Water in a City
    Travelling Salesperson
    Robbers Dilemma

    Mapping to Models
    Combinatorial, Matrices, Graphs, Logic, Constraint
    Satisfaction / Optimization Framework, ILP

    Basic Steps Towards A


    Structured Algorithm Design

    Initial Solution
    Solution Space Creation
    Solution Space Explorations
    Analysis of Complexity
    Finalization of Options
    Data Structuring

    Detailing the Process

    Initial Solution by Recursive Definition


    Analysis by Recurrence Relations
    Asymptotic Complexity
    Opening up the Recursion Space
    Traversal of the Recursion Space
    Optimal Choice / Balancing the
    recursion
    Choosing the final solution
    Identifying need / sources for
    memorization
    Data Structuring

    Demonstration by
    Examples
    Finding the largest
    of n integers

    Largest and Smallest


    Largest and second largest
    Finding Fibonacci Numbers
    Sorting and Searching
    (Route Planning) Shortest Path
    (Telephone Post Wiring) Spanning Tree (What
    about the Telephone Post Placement?)
    (Stamp Selection Problem) Sub-Set Sum
    (Water Pumping) Max Flow Problem
    (Time Table Scheduling) Constraint
    Satisfaction
    Travelling Salesperson

    Efficient Algorithms, Hard


    Problems

    Time and Space Complexity


    Asymptotic Complexity
    Use Trick Questions

    Adding arbitrarily large numbers


    The n = 2*n loop

    Space and Recursion


    Output sensitive algorithms (Tower of Hanoi)

    Polynomial Time Algorithms


    Polynomial Space Algorithms
    Hard Problems
    NP Complete, NP Hard
    Exponential Time
    Exponential Space

    Approximation
    Randomization

    Thank You

    You might also like