Scribd Logo
Upload

Welcome to Scribd!

  • 12 views

    Dsa Assignment

    Uploaded by

    Anchitya Kumar
    The document compares different matrix multiplication and Fibonacci sequence algorithms. It analyzes the performance of one-dimensional, regular, and row-wise matrix multiplication. Regular and row-wise multiplication improve cache locality compared to one-dimensional. It also analyzes recursive and iterative Fibonacci algorithms. Recursive Fibonacci has exponential time complexity due to redundant function calls, while iterative has linear time complexity by directly updating values in a loop.

    Copyright:

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

    Dsa Assignment

    Uploaded by

    Anchitya Kumar
    12 views7 pages
    The document compares different matrix multiplication and Fibonacci sequence algorithms. It analyzes the performance of one-dimensional, regular, and row-wise matrix multiplication. Regular and row-wise multiplication improve cache locality compared to one-dimensional. It also analyzes recursive and iterative Fibonacci algorithms. Recursive Fibonacci has exponential time complexity due to redundant function calls, while iterative has linear time complexity by directly updating values in a loop.

    Original Title

    DSA ASSIGNMENT

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document compares different matrix multiplication and Fibonacci sequence algorithms. It analyzes the performance of one-dimensional, regular, and row-wise matrix multiplication. Regular and row-wise multiplication improve cache locality compared to one-dimensional. It also analyzes recursive and iterative Fibonacci algorithms. Recursive Fibonacci has exponential time complexity due to redundant function calls, while iterative has linear time complexity by directly updating values in a loop.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    12 views7 pages

    Dsa Assignment

    Uploaded by

    Anchitya Kumar
    The document compares different matrix multiplication and Fibonacci sequence algorithms. It analyzes the performance of one-dimensional, regular, and row-wise matrix multiplication. Regular and row-wise multiplication improve cache locality compared to one-dimensional. It also analyzes recursive and iterative Fibonacci algorithms. Recursive Fibonacci has exponential time complexity due to redundant function calls, while iterative has linear time complexity by directly updating values in a loop.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    of 7

    DSA ASSIGNMENT-1

    Matrix Multiplication

    Plots:

    The above provided is the averaged data of the elapsed time of the function. The order of
    matrix changes between 0 and 1500 and vary with every 100.
    The below is the graph for Normal Matrix Multiplication

    The Graph below is for rowRow matrix Multiplication matrix.


    The Graph below is for One Dimensional (matrix Flattening) Algorithm

    The below graph compares all three of them.


    Analysis:
    One-dimensional (1D) matrix multiplication, regular matrix multiplication, and
    row-wise matrix multiplication all have different performance levels. This is
    because of how data is viewed in memory and how well the method uses the
    way the CPU cache works.

    Multiplication in one dimension (1D):


     It shows the parts of a matrix in a one-dimensional grid, where they are
    kept in order.
     When you visit elements in a 1D array, you might make memory calls
    that aren't consecutive, which can make the cache less useful.
     If you don't use your cache well, you might have cache misses, which
    means the CPU has to get data from slower memory, which adds to the
    delay.

    Regular Multiplication of Matrixes:


     There is a 2D array model for regular matrix multiplication. Elements are
    stored in a way that matches the row-column layout of the matrix.
     This can improve cache locality because it means that reading items in a
    row or column usually means accessing memory all at once.
     Having better cache placement can make speed better and cut down on
    cache misses.

    Multiplication by rows in a matrix:


     When you do row-wise matrix multiplication, you use the fact that the
    elements of the final matrix are generated one row at a time.
     In a way similar to standard matrix multiplication, this method can
    improve cache location.
     The method is made to quickly read and process whole rows at once,
    which can make it better for caches.
    Fibonacci Sequence

    The data on the right are the values of time


    Elapsed of the Fibonacci functions both
    iterative and recursive
    The graph below is for the same data provided above

    The above graph is for F(n) vs n

    Analysis:
    Recursive Fibonacci:

     The recursive Fibonacci algorithm has an exponential time complexity,


    specifically O(2^n).
     Each recursive call branches into two additional recursive calls, leading to
    an exponential growth in the number of function calls and redundant
    calculations.
     As n increases, the number of function calls and duplicate calculations
    grows rapidly.

    iterative Fibonacci:

     The iterative Fibonacci algorithm has a linear time complexity,


    specifically O(n).
     It uses a simple loop structure to calculate Fibonacci numbers iteratively
    in a bottom-up manner, directly updating values.
     The iterative approach avoids the exponential growth of redundant
    calculations seen in the recursive approach.

    You might also like