B.Tech.
CSE 4th Semester
CSPC-206 Design and Analysis of Algorithms
Quiz 1
Max Marks: 15 Duration: 30 Mins
Name: Roll No:
Instructions:
• Only answers written with “Black/Blue PEN” in “Answer Space” adjust to every question
will be evaluated.
• There is NO negative marking.
1 Consider the following two functions. What is Answer 1
the time complexity of the function given
(1 below?
marks) int fun1(int n)
{
if (n <= 1) return n;
return 2*fun1(n-1);
}
2 Which of the given options provides the increasing order of asymptotic complexity of
(1 functions f1, f2, f3, and f4?
marks) f1(n) = 2n
f2(n) = n(3/2)
f3(n) = n*log(n)
f4(n) = nlog(n)
A. f3, f2, f4, f1 Answer 2:
B. f3, f2, f1, f4
C. f2, f3, f1, f4
D. f2, f3, f4, f1
3 How many solution/solutions for shortest path problem using bellman ford are available for
(1 a graph having negative weight cycle?
mark) A. One solution Answer 3:
B. Two Solution
C. No Solution
D. Infinite Solutions
4 Fill the table given below for the following graph in the process of detection of articulation
(2 points.
marks)
0 1 2 3 4 5 6 7
Discovery
Time
Low
Time
5 Which of the following is not O(n2)?
(1 A. (15) * n2 Answer 5:
mark) B. n1.98
C. n3/(sqrt(n))
D. (20) * n2
B.Tech. CSE 4th Semester
CSPC-206 Design and Analysis of Algorithms
Quiz 1
Max Marks: 15 Duration: 30 Mins
Name: Roll No:
6. Examine the graph provided and determine the valid combinations within the given breadth-first search
traversal. [Starting from Node “A”]
(1 Answer 6:
mark) A) ABCDGFEIJK
B) ABCDFGEIJK
C) ACBDGFEIJK
D) OPTION A And C
E) None of these
7 Determine the count of all potential pairs in the breadth-first search traversal of the graph mentioned
(1 in the previous question (Q6). Consider the starting node as 'A' and the ending node as 'I'.
mark) A) 6 Answer 7:
B) 7
C) 8
D) None of these
8 Suppose we have an algorithm that takes O(n) time to find the median of an unsorted array. Now
(1 consider a Quicksort implementation where we first find the median using the above algorithm and
mark) then use the median as a pivot. What will be the worst-case time complexity of this modified Quicksort?
A) logn Answer 8:
B) nlogn
C) n^2
D) None of these
9 Considering the graph provided below, our goal is to identify the existence of a negative cycle
(2 by applying the Bellman-Ford algorithm. Select the option that represents a subset of vertices
marks)
for which the Bellman-Ford algorithm will detect the presence of a negative cycle.
A) D F E Answer 9:
B) B F E
C) B D E
D) D E F
10 What is the time complexity of this recurrence relation where Answer 10:
(1 T(n)=2T(n/2)+n ^0.51
mark)
A) O(n) C) O(n^2)
B) O(n^0.51) D) None of These
B.Tech. CSE 4th Semester
CSPC-206 Design and Analysis of Algorithms
Quiz 1
Max Marks: 15 Duration: 30 Mins
Name: Roll No:
Q11 An undirected graph G has n nodes. Its adjacency matrix is given by an n Answer 11
(1 × n square matrix whose (i) diagonal elements are 0‘s and (ii) non-
marks) diagonal elements are 1‘s. which one of the following is TRUE?
A) Graph G has no minimum spanning tree (MST)
B) Graph G has a unique MST of cost n-1
C) Graph G has multiple distinct MSTs, each of cost n-1
D) Graph G has multiple spanning trees of different costs
Q12 Write the correct sequence of points achieved by applying convex Answer 12
(2 hull algorithm?
marks)
******
B.Tech. CSE 4th Semester
CSPC-206 Design and Analysis of Algorithms
Quiz 2
Max Marks: 15 Duration: 30 Mins
Name: Roll No:
Instructions:
• Only answers written with “Black/Blue PEN” in “Answer Space” adjust to every question will be
evaluated.
• There is NO negative marking.
1 Consider the following statements
I. For every weighted graph and any two vertices s and t, the Bellman-ford algorithm starting at
(1 s will always return a shortest path to t.
marks) II. At the termination of the Bellman-ford algorithm, even if a graph has a negative weight cycle,
a correct shortest path is found for a vertex for which the shortest path is well-defined.
Which of the above statements are true?
A. Only I B. Only II Answer 1
C. Both I and II D. None of these
2 Consider n jobs J1, J2..., Jn such that job Ji has execution time ti and a non-negative integer weight Wi. The
(1 weighted mean completion time of the jobs is defined to be ∑!"#$ 𝑤𝑖𝑇𝑖 / ∑!"#$ 𝑤𝑖 where Ti is the completion
marks) time of job Ji. Assuming that there is only one processor available, in what order must the jobs be executed
to minimize the weighted mean completion time of the jobs?
A. Non-decreasing order of ti Answer 2:
B. Non-increasing order of Wi
C. Non-increasing order of witi
D. Non-increasing order of wi/ti
3 Suppose P, Q, R, S, T are sorted sequences having lengths of 20,24,30,35,50 respectively. They are to be
(1 merged into a single sequence by merging two sequences at a time. The number of comparisons that will be
mark) needed in the worst case by the optimal algorithm for doing this is?
A. 350 B. 358 Answer 3:
C. 355 D. 340
4 Consider the weights and values of items listed below. Note that there is only one unit of each item.
(2 Item Number Weight in (Kg) Value in (Rs)
marks) 1 10 60
2 7 28
3 4 20
4 2 24
The task is to pick a subset of these items such that their total weight is not more than 11 Kgs and their total
value is maximized. Moreover, no item may be split. The total value of items picked by an Dynamic
Programming is denoted by V(opt). A greedy algorithm sorts the items by their value- to-weight ratios in
descending order and packs them greedily, starting from the first item in the ordered list. The total value of
items picked by the greedy algorithm is denoted by V (greedy). The value of V(opt)-V(greedy) is?
A. 14 B. 13 Answer 4
C. 16 D. 15
5 Let A1, A2 A3 and A4 be four matrices of dimensions 10 x 5, 5 x 20, 20 x 10, and 10 x 5. respectively. The
(1 minimum number of scalar multiplications required to find the product A1, A2, A3, A4 using the basic
mark) matrix multiplication method is?
A. 1600 B. 1500 C. 1550 D. 1570 Answer 5:
6. Consider two strings A = "qpqrr" and B = "pqprqrp". Let x be the length of the longest Answer 6:
common subsequence (not necessarily contiguous) between A and B and let y be the
(2 number of such longest common subsequences between A and B. Then x +10y =
mark)
A. 34 B. 33 C. 35 D. 40
7 Consider a message composed of the characters {A, B, C, D, E} with frequencies given as follows (A-10,
(1 B-15, C-12, D-3, E-5) Calculate the average number of bits per character for the Huffman code.
mark) A. 2.2 B. 2.5 Answer 7:
C. 2.8 D. 3
B.Tech. CSE 4th Semester
CSPC-206 Design and Analysis of Algorithms
Quiz 2
Max Marks: 15 Duration: 30 Mins
Name: Roll No:
8 Suppose the latter “a”, “b”, “c”, “d”, “e” has probabilities “1/2”, “1/4”, “1/8”, “1/16”, “1/32” respectively.
(1 Then which of the following is the Huffman code for the letters “a”, “b”, “c”, “d”, “e”?
mark) A. 0, 10, 110, 1110, 1111 Answer 8:
B. 11, 10, 011, 010, 001
C. 11, 10, 01, 0011, 0001
D. 110, 100, 010, 000, 001
9 Which of the following problems is equivalent to the 0-1 Knapsack problem?
(2 A) You are given a bag that can carry a maximum weight of W. You are given N Answer 9:
marks) items which have a weight of {w1, w2, w3,…., wn} and a value of {v1, v2, v3,….,
vn}. You can break the items into smaller pieces. Choose the items in such a way
that you get the maximum value
B) You are studying for an exam and you have to study N questions. The questions
take {t1, t2, t3,…., tn} time(in hours) and carry {m1, m2, m3,…., mn} marks. You
can study for a maximum of T hours. You can either study a question or leave it.
Choose the questions in such a way that your score is maximized
C) You are given infinite coins of denominations {v1, v2, v3,….., vn} and a sum
S. You have to find the minimum number of coins required to get the sum S
D) You are given a suitcase that can carry a maximum weight of 15kg. You are
given 4 items which have a weight of {10, 20, 15,40} and a value of {1, 2, 3,4}.
You can break the items into smaller pieces. Choose the items in such a way that
you get the maximum value
10 Suppose two activities A and B, having start and finish time as SA, FA and SB, FB Answer 10:
(1 respectively. Both the activities are said to be compatible, under which of the
mark) following condition?
a) SA = FB
b) SA > FB
c) SA >= FB or SB >= FA
d) SA >= FB and SB = FA
Q11 Consider the following number of activities with their start and finish time given Answer 11
below. In which sequence will the activity be selected in order to maximize the
(2 number of activities, without any conflicts?
marks)
******
B.Tech. CSE 4th Semester
CSPC-206 Design and Analysis of Algorithms
Quiz 3
Max Marks: 15 Duration: 25 Mins
Name: Roll No:
Instructions:
• Only answers written with “Black/Blue PEN” adjust to every question will be evaluated.
• There is NO negative marking.
1
(3
marks)
2 In the context of the N-Queen problem, which gate-level logic operation best
(2 represents the constraint of ensuring that no two queens threaten each other along
marks)
the same row, column, or diagonal?
A) AND gate B) OR gate
C) XOR gate D) NOT gate
3
(3
mark)
4 Given an array of positive integers A= [2,3,5] and target=18, find the count of all
(2 unique combinations (power set) of numbers in the array that sum up to the target.
marks)
A)3 B)5
C)8 D)9
B.Tech. CSE 4th Semester
CSPC-206 Design and Analysis of Algorithms
Quiz 3
Max Marks: 15 Duration: 25 Mins
Name: Roll No:
5 An algorithm to find the length of the longest monotonically increasing sequence
(2 of numbers in an array A[0 :n-1] is given below. Let Li denote the length of the
mark)
longest monotonically increasing sequence starting at index i in the array.
Which of the following statements is TRUE?
(A)The algorithm uses dynamic programming paradigm
(B)The algorithm has a linear complexity and uses branch and bound paradigm
(C)The algorithm has a non-linear polynomial complexity and uses branch and
bound paradigm
(D)The algorithm uses divide and conquer paradigm.
6. 12.
Consider the weights and values of items listed below. Note that there is only one
(3
unit of each item.
mark)
Item No 1 2 3 4
Weight(Kg) 10 7 4 2
Value 60 28 20 24
The task is to pick a subset of these items such that their total weight is not more
than 11 kgs and their total value is maximized. Moreover, no item may be split. The
total items picked by an optimal solution is denoted by Vopt. A greedy algorithm sorts
the item by their value-to-weight ratios in decreasing order and packs them greedly
starting from the first item in the ordered list. The total value of items picked by
greedy algorithm is denoted by Vgreedy. The value of Vopt- Vgreedy is?
A) 12
B)14
C)16
D)10
******
B. Tech CS 4th Semester.
CSPC- 206 Design and analysis and Algorithm
Assignment
Max Marks: 10 Duration: 20 Mins
Name: Roll No:
Instructions:
• Only answers written with “Black/Blue” in “Answer Space” adjacent to every question will
be evaluated.
• There is NO negative marking
1. Consider the following undirected graph on 5 nodes
Assume you are performing breadth-first search on this graph using a queue data structure.
How many unique breadth first orderings are possible?
A) 9 Answer:
B) 24
C) 48
D) 120
2. Suppose P,Q,R,S,T are sorted sequences having length 20 24 30 35 50 respectively. They are
to be merged into a single sequence by merging together two sequences at a time. The number
of comparisons that will be needed in the worst case by optimal algorithm for doing this is:-
A) 350 Answer:
B) 358
C) 362
D) 357
3. Consider an already sorted array of size n and a number x. What is the time complexity for the
best-known algorithm to find a triplet with a sum equal to x? For reference, arr[] = {1, 5, 10,
15, 20, 30} and x = 40. Then we have a triplet {5, 15, 20} with a sum of 40.
A) O(n) Answer:
B) O(n^2)
C) O(n logn)
D) O(n^3)
4. f(n) = o(g(n)) implies
A) 0 <= f(n) <= Cg(n) such that there exists some positive Answer:
constant C & n 0 > ∀n >= n0
B) 0 <= f(n) < Cg(n) for every +ve constant C > 0 there
exisxts n_{0} > 0, ∀n >= n0
C) 0 <= C1, f(n) <= C2*g(n) ∀n >= n0 such that C1, C2 &
n0 are +ve constants
D) None of the above
5. Find the recurrence relation of the following code using master’s theorem and find its time
complexity.
1. A(n)
2. {
3. if(n<=1)
4. return 1;
5. else
6. return A(√n);
7. }
A) T(n)=𝜃(log2n) Answer:
B) T(n)= 𝜃(log2log2n)
C) T(n)=𝜃(nlog2n)
D) T(n)= 𝜃(n2log2n)
6. If the binary search algorithm determines that the search argument is in the upper half of the
array, which of the following statements will set the appropriate variable to the appropriate
value?
A) Start sub = middle sub-1 Answer:
B) Start sub = middle sub+1;
C) Stop sub = middle sub-1
D) Stop sub = middle sub+1
7. State whether the following statements are false:
A) If e is a minimum edge weight in a connected weighted Answer:
graph, it must be among the edges of at least one minimum
spanning tree of the graph.
B) If e is a minimum edge weight in a connected weighted
graph, it must be among the edges of each one minimum
spanning tree of the graph.
C) If edge weights of a connected weighted graph are all
distinct, the graph must have exactly one minimum
spanning tree. T
D) If edge weights of a connected weighted graph are not all
distinct, the graph must have more than one minimum
spanning tree.
E) If edge weights of a connected weighted graph are not all
distinct, the minimum cost of each one minimum spanning
tree is same.
8. Running time of 0/1 knapsack problem using dynamic programming is Assume n is the number
of items and w is the capacity of knapsack.
A) O(n^2) Answer:
B) O(n^w)
C) O(w^n)
D) O(nw)
9. This of the following algorithm allows negative edge weight in a graph to find shortest path?
A) Dijkstra’s algorithm Answer:
B) Bellman ford algorithm
C) Kruskal algorithm
D) Prim’s algorithm
10. Merge sort uses:
A) Divide and conquer strategy Answer:
B) Backtracking Approach
C) Dynamic programming Approach
D) Greedy Approach
