Scribd Logo
Upload

Welcome to Scribd!

  • 2 views

    lecture4

    Uploaded by

    mustaqeemarshad488

    Copyright:

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

    lecture4

    Uploaded by

    mustaqeemarshad488
    2 views16 pages

    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
    2 views16 pages

    lecture4

    Uploaded by

    mustaqeemarshad488

    Copyright:

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

    CSI-402: Data Structure and Algorithms

    Algorithms, Characteristics, Types


    ALGORITHM

    The step-by-step procedure for solving a problem is called an


    algorithm. It also specifies the sequence in which these steps
    are executed for solving the problem. It terminates after a finite
    number of steps.
    In an algorithm, the problem is divided into a number of simple
    steps. These steps are arranged in an order. Each step is
    solved independently. The solution of all steps in an order gives
    the solution of the problem.
    The steps of an algorithm are written in human understandable
    language and are independent of a particular programming
    language. Algorithm is the general solution of the problem.

    CSI 402 2024 2


    ALGORITHM

    After writing the algorithm, it can be implemented in any


    programming language. It means that a program is written in a
    programming language by following the algorithm of the
    problem. We will use C++ for implementing the algorithms.
    There may be multiple solutions of a given problem. Hence many
    algorithms can be derived for the solution of a problem. Always
    the best algorithm is selected for the solution of the problem.

    CSI 402 2024 3


    Characteristics of an Algorithm

    Please note that any procedure cannot be called an algorithm. An


    algorithm must have the following characteristics / features:

    Beginning and End: An algorithm has a definite beginning and


    end.
    Unambiguous: The word ' 'unambiguous" means "clear-cut" or
    "definite". An algorithm should be clear and precise. Each step
    of an algorithm must be clearly defined and must lead to only
    one meaning.
    Input: An algorithm may have many inputs. It takes action on
    input(s) to achieve the required result.

    CSI 402 2024 4


    Characteristics of an Algorithm

    Output: An algorithm has at least one output (or result). However,


    it may have more than one output.
    Finiteness: An algorithm must terminate after a finite number of
    steps.
    Independent: An algorithm should be independent of any
    programming language.
    Feasibility: An algorithm should be feasible with the available
    resources.

    CSI 402 2024 5


    Types of Algorithms

    There are various types of algorithms. Following are some


    important types of algorithms:
    1) Linear Algorithm
    A linear algorithm is one of the most basic algorithm to find a
    particular element in a list of elements. It sequentially checks
    each element of the list for the target element or value until a
    match is found or until all the elements have been searched. For
    example, a linear algorithm is used to count "how many times a
    specific value exist in a list". Similarly, adding up all the numbers
    in an array is another example of linear algorithm.
    Linear algorithm is practical when the list has only a few elements,
    or when performing a single search in an unsorted list.
    However, linear algorithm is not practical for performing
    operations on lists with large elements.

    CSI 402 2024 6


    Types of Algorithms

    2) Divide and Conquer


    The "divide and conquer" is a type of algorithm which divides the
    problem into sub-problems (pieces) and solves these sub-
    problems one by one. The solutions of the sub-problems are
    combined to get the final solution.

    The divide and conquer has three parts:


    i) Divide or Break: In this step, problem is divided into smaller sub.
    problems. Normally, the sub-problems are similar to the original
    problem.
    ii) Conquer or Solve: In this step, the solutions of the sub-problems
    are solved recursively.

    CSI 402 2024 7


    Types of Algorithms

    iii) Merge or Combine: In this step, the solutions of the sub-


    problems are combined to get the solution of the original
    problem.

    For example, "Merge Sort" algorithm is based on divide-and-


    conquer programming approach. In order to sort an array, this
    algorithm divides the array into two halves, recursively sorts
    them and then merges the two sorted halves.

    CSI 402 2024 8


    Types of Algorithms

    3) Greedy Algorithm
    In this type of algorithm, we try to solve problems by selecting the
    best piece first and then working on the other pieces. For
    example, to find the largest value in an array, fry finding the
    largest object first and then the smaller one later. Another
    example of greedy algorithm is "counting coins". Suppose you
    are provided coins of Rs. 1, 2, 5, and 10 and you are asked to
    count the amount of all coins. The greedy procedure will be as
    follows:
    i) Select Rs. 10 coin.
    ii) Select Rs. 5 coin.
    iii) Select Rs. 2 coin.
    iv) Select Rs. 1 coin.

    CSI 402 2024 9


    Types of Algorithms

    4) Iterative Algorithm
    In this type of algorithm, in order to obtain the required result, we
    start with a value and repeatedly change it in the direction of the
    solution. For example, to calculate the factorial of a given
    number, we start with the number and continue to decrease the
    number through the algorithm till the number reaches to zero.

    CSI 402 2024 10


    WRITING ALGORITHMS

    There is no well-defined standard for writing an algorithm. Rather, it


    is problem and resource dependent. Algorithms are never
    written to support a particular programming language. All
    programming languages share basic code constructs like
    input/output statements, loops, selection statements (flow-
    control) etc. These common constructs can be used to write an
    algorithm.

    An algorithm is normally written in step by step manner.

    CSI 402 2024 11


    WRITING ALGORITHMS

    Example:
    Following algorithm inputs values in variables A, B and C. It adds
    these values and displays result.
    STEP 1- START
    STEP 2- INPUT VALUE IN, A
    STEP 3- INPUT VALUE IN B
    STEP 4- INPUT VALUE IN C
    STEP 5- SUM = A + B + C
    STEP 6- PRINT SUM
    STEP 7- END

    CSI 402 2024 12


    ALGORITHM ANALYSIS

    Once an algorithm is written for a problem and decided to be


    correct, the next important step is to analyze the algorithm.
    Algorithm analysis is the determination of the amount of
    resources such as memory (space or storage) and time
    requirements (complexity) necessary to execute the algorithm
    i.e. program. Most of the algorithms are designed to work with
    inputs of arbitrary length. Usually, the efficiency or running time
    of an algorithm is stated as a function relating the input length to
    the number of steps (time complexity) or storage locations
    (space complexity).

    CSI 402 2024 13


    ALGORITHM ANALYSIS

    Efficiency of an algorithm can be analyzed at two different stages


    i.e. before and after implementation. These stages are as
    follows:
    A Priori Analysis: This is the theoretical analysis of an algorithm.
    Efficiency of an algorithm is measured by assuming that all
    other factors (such as processor speed) are constant and have
    no effect on the implementation.
    A Posterior Analysis: This is the empirical (or experimental)
    analysis of an algorithm. The selected algorithm is implemented
    using programming language. It is then executed on target
    computer. In this analysis, actual running time and space
    required are collected.

    CSI 402 2024 14


    ALGORITHM COMPLEXITY

    Complexity of an algorithm is a measurement of the amount of


    running time and / or storage space required by an algorithm for
    an input of a given size (n). An algorithm is said to be efficient
    and fast; if it takes less time to execute and consumes less
    memory space.
    Time Complexity of an algorithm represents the amount of time
    required by the algorithm to complete its task or execution. Time
    Complexity is mostly estimated by counting the number of
    elementary functions performed by the algorithm. However, the
    performance of an algorithm may vary with different types of
    input data.

    CSI 402 2024 15


    ALGORITHM COMPLEXITY

    Space Complexity of an algorithm represents the amount of


    memory space required by the algorithm to complete its task or
    execution. The amount of storage space required by an
    algorithm varies with the size of the problem to be solved.
    Space required by an algorithm is equal to the sum of the
    following:
    • A fixed amount of memory space for the program code, simple
    variables and constants used in the program. These are
    independent of the size of the problem being solved.
    • A variable amount of memory space required by variables
    whose size is dependent on the problem being solved. This
    space increases or decreases if the problem uses dynamic
    memory allocation, recursion stack space etc.

    CSI 402 2024 16

    You might also like