Academic Task No.

Name of the faculty member:

Course Code:
Course Title: DESIGN AND ANALYSIS OF ALGORITHMS (CSE230)
Program: B-Tech Term:
Max. Marks: 30 Is Rubric Applicable: NA
Date of Allotment: 20.09.2021 Date of Submission: 27.09.2021

Important Guidelines:
1. All questions in this Academic Task are compulsory.
2. It is mandatory to attempt all questions of the assignment in your own handwriting on A4 size
sheets/pages with a blue colour ink pen. Any other mode of attempt (typed or printed codes or table) except
hand written/drawn will not be accepted/considered as valid submission(s) under any circumstances.
3. Every attempted sheet/page should carry clear details of student such as Name, Registration number,
Roll number, Question number and Page number. The page numbers should be written clearly on the
bottom of every attempted sheet in a prescribed format as: for page 1; Page 1 of 4, for page 2; Page 2 of 4,
for page 3; Page 3 of 4 and for page 4; Page 4 of 4, in case your assignment/document is of 4 pages.
4. After attempting the answer(s), student needs to take photograph of each of these answer sheets/pages
and needs to convert the jpeg format images into a single pdf format document (can be done with many
free online available converters).
5. This PDF file should be uploaded onto the UMS interface on or before the last date of the
submission.

6. Refrain from indulging into plagiarism as copy cases will be marked zero.

7. This Document contains 2 sets of Paper, namely Set A and Set B

8. Set A is for learners having Odd Roll Number and Set B is for learners having Even Roll
Number. Learners must solve and upload papers accordingly. Solving a wrong set would be
consider a failed attempt to solve CA1 and will be given 0 marks.

Set A
Q.1. Choose the correct option - 10 mark

1. What is the recurrence relation for the optimal time of Tower of Hanoi with n discs?

A. T(n) = 2T(n/2) + 1
B. T(n) = 2T(n/2) + n
C. T(n) = 2T(n-1) + 1
D. T(n) = 2T(n-2) + n
2. What will be the time complexity of the following code?
public static int test(int n) {

int x = 0;
for(int i=0;i<n;i++) {
for(int j=i;j>0;j--)
x++;
}
return x;
}

A. O(n)
B. O(n^2)
C. O(nLognLogn)
D. O(nLogn)

3. Given an array arr = {15,57,36,80,49,6,98} and key = 98; What will be the middle values(corresponding
array elements) generated in the first and second iterations?

A. 80 and 6
B. 80 and 98
C. 36 and 49
D. 49 and 6

4. What will be the space complexity of the following function?

public static double test (int n){
double x;
if (n == 0) return 1.0;
else
{
x = 0.0;
for (int i = 0; i < n; i++)
x += test(i);
return x;
}
}

A. O(1)
B. O(n)
C. O(2^n)
D. O(n!)
5. What will be the time complexity of following code in terms of n?
for(int i = 0; i < n ; i++){
int k = n;
while(k > 0){
k/=2;
}
}

A. O(nk)
B. O(n)
C. O(n^2)
D. O(nlogn)

Q.2. Short answer type question? 10 marks

1. What is recursion? How does

it work and how is it related to the Principle of Mathematical Induction?
2. Explain the different asymptotic notations.

Q.3. Long answer Type question. 10 marks

1. Given an integer n, using phone keypad find out and print all the possible strings that can be made using
digits of input n.

Sample Input 1: 23

Sample Output 1:

ad
ae
af
bd
be
bf
cd
ce
cf

Explanation: In phone keypad, 2 = “abc” and 3 = “def” so the different combinations that can be made are
ad,ae,af,bd,be,bf,cd,ce,cf.
Sample Input 2: 8

Sample Output 2:
t
u
v

2. Given 2 sorted arrays (in increasing order), find a path through the intersection that produces the
maximum sum and return the maximum sum. That is, we can switch from one array to another array only at
common elements. If no intersection element is present, we need to take the sum of all elements from the
array with greater sum.

Sample Input:

6
1 5 10 15 20 25
5
2 4 5 9 15

Sample Output :
81

Explanation :
We start from array 2 and take sum till 5 (sum = 11). Then we'll switch to array at element 10 and take till
15. So sum = 36. Now, no elements are left in array after 15, so we'll continue in array 1. Hence the sum is
81.

Set B
Q.1. Choose the correct option 10 mark

1. What is the recurrence relation for worst case of Binary Search?

A. T(n) = T(n-1) + O(1)

B. T(n) = 2T(n/2) + O(1)
C. T(n) = T(n-2) + O(1)
D. T(n) = T(n/2) + O(1)

2. What will be the time complexity of the following code?

public static int test(int n) {

int x = 0;
for(int i = n ; i > 0 ; i /= 2) {
for(int j = 0 ; j < i ; j++)
x++;
}
return x;
}
 A. O(n)
B. O(n^2)
C. O(nLognLogn)
D. O(nLogn)

3. Which of the following options provides the ascending order of asymptotic complexity of functions f1,
f2, f3 and f4?
f1(n) = 2^n
f2(n) = n^(3/2)
f3(n) = nLogn
f4(n) = n^(Logn)

A. f3 < f2 < f1 < f4

B. f2 < f3 < f1 < f4
C. f2 < f3 < f4 < f1
D. f3 < f2 < f4 < f1

4. What will be the time complexities of the following two functions?

public static int test1(int n){
if (n <= 1)
return n;
return 2*test1(n-1);
}

public static int test2(int n){

if (n <= 1)
return n;
return test2(n-1) + test2(n-1);
}

A. O(n^2) for test1() and O(2^n) for test2()

B. O(2^n) for both test1() and test2()
C. O(n) for test1() and O(2^n) for test2()
D. O(n) for both test1() and test2()

5. What will be the time complexity of following code in terms of n?

public static void test(int n){
int sum=0;
for(int i=1;i<n;i++) {
for(;i<n*n;i++){
sum+=i;
}
 }
System.out.println(sum);
}

A. O(n)
B. O(n^2)
C. O(n^3)
D. O(n^4)

Q.2. Short answer type question? 10 marks

1. How do you measure the efficiency of an algorithm? Explain in detail.

2. What is divide and conquer approach? Explain the working of binary search algorithm in detail.

Q.3. Long answer Type question. 10 marks

1. You are given N number of intervals, where each interval contains two integers denoting the start time
and the end time for the interval. The task is to merge all the overlapping intervals and return the list of merged
intervals sorted by increasing order of their start time.

Two intervals [A,B] and [C,D] are said to be overlapping with each other if there is at least one integer that is covered
by both of them.

Input Format:

The first line of input contains an integer N, the number of intervals.

The second line of input contains N integers, i.e. all the start times of the N intervals.

The third line of input contains N integers, i.e. all the end times of the N intervals.

Output Format:

Print the final list of merged intervals

Sample Input 1:
5
1 3 6 8 10
4 5 8 9 12

Sample Output 1:
15
69
10 12
Explanation:

For the given 5 intervals - [1, 4], [3, 5], [6, 8], [8, 9], [10, 12]

Since intervals [1, 4] and [3, 5] overlap with each other, we will merge them into a single interval as [1, 5].

Similarly, [6, 8] and [8, 9] overlap, merge them into [6,9].

Interval [10, 12] does not overlap with any interval.

Final List after merging overlapping intervals: [1, 5], [6, 9], [10, 12].

2. Assume that the value of the alphabet a = 1, b = 2, c = 3, ... , z = 26. You are given a numeric string S.
Write a program to print the list of all possible codes that can be generated from the given string.

Sample Input:
1123

Sample Output:
aabc
kbc
alc
aaw
kw