Scribd
Upload
8 views

Algorithms Mid-1 3

Uploaded by

maira
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
8 views

Algorithms Mid-1 3

Uploaded by

maira
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 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