Scribd Logo
Upload

Welcome to Scribd!

  • 5 views

    BCS-42 June 2022

    Uploaded by

    bgtes123

    Copyright:

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

    BCS-42 June 2022

    Uploaded by

    bgtes123
    5 views3 pages

    Original Title

    BCS-42 june 2022

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    5 views3 pages

    BCS-42 June 2022

    Uploaded by

    bgtes123

    Copyright:

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

    No.

    of Printed Pages : 3 BCS-042

    BACHELOR OF COMPUTER APPLICATIONS


    (BCA) (Revised)
    Term-End Examination
    June, 2022

    BCS-042 : INTRODUCTION TO ALGORITHM DESIGN

    Time : 2 hours Maximum Marks : 50


    Note : Question no. 1 is compulsory and carries
    20 marks. Answer any three questions from the
    rest.

    1. (a) Define basic efficiency classes in context of


    running time. 3

    (b) Perform linear and binary search to find


    15 in a given list of numbers as below :
    5 7 9 12 13 15 21 25

    Count the number of comparisons in both


    the search methods. 6

    (c) Define a recurrence relation. Draw a


    recurrence tree for the following recurrence
    relation : 5
    T(n) = 2T(n/2) + 1

    BCS-042 1 P.T.O.
    (d) Apply Kruskal’s algorithm to find out the
    minimum cost spanning tree. 6

    Starting vertex is A.

    2. (a) Arrange the following functions in


    increasing order : 2
    n n
    log 2 , n log 2 , n2, 5n + 7

    (b) List any two applications of BFS/DFS. 2


    (c) Write the algorithm for left to right binary
    exponentiation evaluation and apply the
    algorithm for evaluating a280. Show all the
    steps. 6

    3. (a) For the function defined by


    f(n) = 6n2 + 8n + 6,
    show that f(n) = O(n2). 4
    (b) Show that Dijkstra’s algorithm may not
    work if edges can have negative weight. 3
    (c) Traverse the complete graph on four
    vertices using BFS and write the sequence
    of vertices that would be visited by the
    graph traversal algorithm. 3

    BCS-042 2
    4. (a) Write a recurrence relation for Fibonacci
    series problem. 3

    (b) Write and apply Mergesort algorithm to


    sort the following list of integer numbers. 7
    Show all the intermediate steps.
    15, 8, 7, 4, 25, 30, 5, 13

    5. (a) Write any two cases of the Master method


    with formal notations. 4

    (b) Write recurrence relations for matrix


    multiplication using Strassen’s method and
    solve it using the Master method. 6

    BCS-042 3 P.T.O.

    You might also like