Scribd Logo
Upload

Welcome to Scribd!

  • 5 views

    Algorithms Mid-1 3

    Uploaded by

    maira

    Copyright:

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

    Algorithms Mid-1 3

    Uploaded by

    maira
    5 views2 pages

    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 views2 pages

    Algorithms Mid-1 3

    Uploaded by

    maira

    Copyright:

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

    National University of Computer and Emerging Sciences, Lahore Campus

    Course Name: Design and Analysis of Algorithms Course Code: CS2009


    Degree Program: BSCS Semester: SPRING 2023
    Exam Date: Monday, February 27, 2023 Total Marks: 24 + 12 = 36
    Section: ALL Page(s): 2
    Exam Type: Mid-Term - I
    Student : Name:_____________________________ Roll No.________________ Section:_______
    Instruction/Notes: Attempt all questions. There are two question, don’t forget to check the back side as well.

    Question 1: [CLO - 2] [4+5+3+3+3+(4+2) = 24 Marks]

    For each part in this question, you are required to analyze the given functions T(n) and
    answer the given question.

    a) For the following function f(n), find a function g(n), such that f(n) = θ (g(n))
    [Hint: For part a you have to provide the constants 𝑛 , 𝑐 , 𝑐 ]

    𝑻(𝒏) = (𝟏𝟎𝟎𝟎)𝟐𝒏 + 𝟒𝒏

    𝒏 𝟒𝒏
    b) Solve the recurrence relation 𝑻(𝒏) = 𝑻 +𝑻 + 𝒏, where 𝑇(1) = 1
    𝟓 𝟓

    [For part b you are required to use recursion tree method]

    𝒏
    c) Solve the recurrence relation 𝑻(𝒏) = 𝟐𝟓𝑻 + 𝒏𝟐 , where 𝑇(1) = 1
    𝟓

    [For part c you can use any method]

    d) Prove or disprove the following statement

    2 𝑖𝑠 𝑂(2 )

    e) Prove or disprove the following statement

    4 𝑖𝑠 𝑂(2 )

    Department of Computer Science Page 1 of 2


    f) Consider the following sorting algorithm:
    MySort(A, 1, 10)
    MergeSort(A, 1, 7)
    MergeSort(A, x, y)
    MergeSort(A, 1, 7)

    i. What should be the minimum value of 𝑦 − 𝑥 + 1, so that MySort(A, 1, 10) correctly


    sorts the 100 elements array given to it as input.
    ii. Based on your answer (for the minimum value of 𝑦 − 𝑥 + 1), what are exact values of
    𝑥 and 𝑦.

    Question 2: [CLO - 1] [12 Marks]

    Let A[1..n] be an array of n distinct numbers. If 𝑖 < 𝑗 and 𝐴[𝑖] < 𝐴[𝑗] then the pair (𝑖, 𝑗) is
    called a compatibility of A. Design an algorithm that determines the number of
    compatibilities in any permutation on n elements in O(𝑛 log 𝑛) worst case time. (Hint:
    Modify merge sort.)

    Department of Computer Science Page 2 of 2

    You might also like