DAA QUESTION BANK ANSWER KEY

PART-B: LONG ANSWERS 10 Marks each

UNIT-I

Q. No Question
a. List the characteristics of an algorithm
b. What is pseudo code?
1
c. List the procedure to be followed to convert a problem into pseudocode with
an example.
a. What are the characteristics of an algorithm?
2 b. Write an algorithm to generate Fibonacci series and find the time
complexity.
a. Define space and time complexity.
3 b. Write an algorithm or pseudo code to sorting n numbers and find the time
complexity.
a. What do you mean by asymptotic notations?
4 b. Define all the asymptotic notations.
c. Prove that 10n2+3n+3 = Ω(n2)
a. Discuss the Master theorem.
5 a. Solve the récurrence relations T(n) = T(n/2) + ½ n2 + n and T(n) = 2T(n/2) +
nlogn
a. What is divide and conquer method?
b. Write the control abstraction of divide and conquer method.
6
What is the time complexity of DANDC while two sub problems are
approximately equal.
a. What is recurrence relation?
b. What are the methods available to solve the recurrence relations?
7
a. Write the pseudo code or algorithm for binary search and time complexity in
worst, average and best case.
a. How to derive the recurrence relation of merge sort?
8 b. Write the pseudo code or algorithm of merge sort and time complexity.
c. 8,3,2,9,7,1,5,4  Apply merge sort and sort the elements
a. Write the pseudo code or algorithm of quick sort and time complexity in best
9 & worst case
b. Apply quick sort algorithm and sort the data: 20, 35, 10, 16, 54, 21, 25
a. Write the pseudo code or algorithm for binary search
10 b. 2,6,8,12,16,22,30  apply binary search to search an element “16” and write
the time complexity
 ANSWERS

1. a) List the characteristics of an algorithm.

b) What is pseudo code?
c) List the procedure to be followed to convert a problem into pseudocode with an example.

Answer:
1. a) Characteristics of an algorithm:
i. Input : Zero or more no. of quantities are given to the algorithm.
ii. Output : The algorithm should produce atleast one quantity, as an output.
iii. Definiteness : Each instruction in algorithm should be clear and unambiguous.
iv. Finiteness : If we trace out the instructions of an algorithm, then for all cases, the algorithm
terminates after a finite number of steps.
v. Effectiveness : Every instruction must be very basic so that it can be carried out, in principle, by
a person using pencil and paper.

1. b) Pseudo code:
 Pseudocode is a programming language independent description of the sequence of steps
necessary to solve a problem.
 Pseudo code is one of the methods that can be used to represent an algorithm.
 Pseudocode is a simple way of writing programming code in English . It is not actual
programming language and does not use the syntax of a specific programming language.
 But it closely resembles the structure of a programming language & contains roughly the same
level of detail.

1. c) Writing Pseudo code:

1. Pseudo code is a procedure consisting of head and body sections.
2. The head section consists of keyword “Algorithm” and name of the algorithm, followed by
parameter list, given as follows:

Algorithm name (<Parameter list>)

3. The body section contains various programming constructs such as “if, for, while” or some
assignment statements.
4. Comments begin with // and continue until the end of line.
5. Blocks are indicated and matching braces: { and }.
6. An identifier begins with a letter & not by a digit.
7. Assignment of values to variables is done using the assignment statement
<variable> := <expression>
8. There are two Boolean values: true and false. In order to produce these values, the logical
operators “and”, “or”, “not(!)”, and relational operators
are used.
9. Elements of multi-dimensional array are accessed using [ and ].
10. The following looping statements are employed: for, while and repeat – until.
 11. A conditional statement has the following forms: if <condition> then <statement>;
12. Input and output are done using the instructions: read and write.
Example: Write algorithm to find sum of n numbers.
Pseudocode: 1 Algorithm sum(a,n)
2 {
3 res: = 0.0;
4 for i:=1 to n do
5 res:= res + a[i];
6 return res;
7 }
Algorithm: Pseudocode to find sum of n-numbers

--------------------------------------------------------------------------------------------------------------------------------------------------------
Q2. a) What are the characteristics of an algorithm?
b) Write an algorithm to generate Fibonacci series and find the time complexity.
Answer:
a) Characteristics of an algorithm:
i. Input : Zero or more no. of quantities are given to the algorithm.
ii. Output : The algorithm should produce atleast one quantity, as an output.
iii. Definiteness : Each instruction in algorithm should be clear and unambiguous.
iv. Finiteness : If we trace out the instructions of an algorithm, then for all cases, the algorithm
terminates after a finite number of steps.
v. Effectiveness : Every instruction must be very basic so that it can be carried out, in principle, by
a person using pencil and paper.

b) Algorithm to generate Fibonacci series:

Frequency Count (FC) Total Steps=FC*s/e
Algorithm Statements s/e
n1 n>1 n1 n>1
1 Algorithm Fibonacci_Series(n) - - - - -
2 { - - - - -
3 if(n  1) then 1 1 1 1 1
4 write (n); 1 1 0 1 0
5 else - - - - -
6 { - - - - -
7 n1:= 0; 1 0 1 0 1
8 n2:= 1; 1 0 1 0 1
9 for i:=2 to n do 1 0 n 0 n
10 { - - - - -
11 n3:= n1 + n2; 1 0 n-1 0 n-1
12 n1:= n2; 1 0 n-1 0 n-1
13 n2:= n3; 1 0 n-1 0 n-1
14 write(n3); 1 0 n-1 0 n-1
15 } - - - - -
16 } - - - - -
17 }
Algorithm: Algorithm to print fibonacci series upto Total Steps: 2 5n - 1
n-numbers.

The Time complexity of the fibonacci series algorithm is O(n).

--------------------------------------------------------------------------------------------------------------------------------------------------------
Q3. a) Define space and time complexity.
b) Write an algorithm or pseudo code to sorting n numbers and find the time complexity.

Answer:
a) Space Complexity : The space complexity of an algorithm is the amount of memory it needs to run to
its completion.
Time complexity : The time complexity of an algorithm is the amount of computer time it needs to
run to its completion.

b) Algorithm to sort n numbers :

Algorithm Statements S/e Frequency Total Steps

1 Algorithm Sort(a,n) - - -
2 //Sort the array a[1:n] into non decreasing order - - -
3 { - - -
4 for i:=1 to n do 1 n+1 n+1
5 { - - -
6 j:= i; 1 n n
7 for k:= i+1 to n do 1 n*(n+1) +n
8 { - - -
9 if (a[k] < a[j]) then 1
10 j:= k; 1
11 } - - -
12 t:= a[i]; 1 n n
13 a[i]:= a[j]; 1 n n
14 a[j]:= t; 1 n n
15 } - - -
16 } - - -
Algorithm: To Sort array elements in non-decreasing order Total Step Count: 3 +6n+1

The Time complexity to sort the array elements algorithm is O( ).

--------------------------------------------------------------------------------------------------------------------------------------------
Q 4. a) What do you mean by asymptotic notations?
b) Define all the asymptotic notations.
c) Prove that 10n2+3n+3 = Ω(n2).

4 a) Answer:
Asymptotic Notations are languages that allow us to analyse an algorithm’s running time by identifying its
behaviour as the input size for the algorithm increases. This is also known as an algorithm’s growth rate.
4 b) Answer:
 There are five different kinds of Asymptotic notations used to represent the time complexity:
1. Big Oh notation (O)
2. Big Omega notation ( Ω )
3. Theta notation ( θ )
4. Little oh notation ( o )
5. Little omega notation ( ω )
 t
1. Big Oh notation (O) :
 The function f(n) = O(g(n)) if and only if there exist positive
constant c and n0 such that f ( n )  c * g(n) for all n, n  n0 .
 Big-O notation represents the upper bound of the running time of n
an algorithm. Thus, it gives the worst-case complexity of an
algorithm.
2. Big Omega notation ( Ω ) :
t
 The function f(n) = Ω (g(n)) if and only if there exist positive
constant c and n0 such that f ( n ) ≥ c * g(n) for all n, n  n0 .
 Omega notation represents the lower bound of the running time of
an algorithm. Thus, it provides the best-case complexity of an
algorithm. n

3. Theta notation ( θ ) :
t
 The function f(n)= θ (g(n)) if and only if there exist
positive constants c1, c2 and no such that
c1*g(n)  f(n)  c2*g(n) for all n, n  n0.
 The above definition states that the function f(n) lies
between c1 times the function g(n) and c2 times the
function g(n) where c1 and c2 are positive constants.
4. Little oh notation ( o ) :
 The function f(n) = o(g(n)) if and only if

5. Little omega notation ( ω ) :

 The function f(n)= ω (g(n)) if and only if for all n, n ≥ 0 .
[For Q 4 (c) refer class notes. ]
---------------------------------------------------------------------------------------------------------------------------------
Q 5. a) Discuss the Master theorem.
b) Solve the récurrence relations T(n) = T(n/2) + ½ n2 + n and
T(n) = 2T(n/2) + nlogn.
Answer: a) Refer DAA class notes for the model questions.
---------------------------------------------------------------------------------------------------------------------------------
Q 6. a) What is divide and conquer method?
b) Write the control abstraction of divide and conquer method.
c) What is the time complexity of DANDC while two sub problems are approximately equal.
Answer:
a) Divide and Conquer method:
 Given a problem, relatively large, divide-and-conquer strategy suggests splitting or dividing the problem
into sub-problems, solving the sub problems and then combining the sub-solutions to get solution to the main
problem.
 If the subproblems are still relatively large, then the divide-and conquer strategy can possibly be reapplied.
b) Control abstraction of divide and conquer method:
 A control abstraction means a procedure whose flow of control is clear but whose primary operations
are specified by other procedures, whose precise meanings are left undefined.

Algorithm:
Explanation:
 In the above algorithm, DAndC(P), “P” is the problem to be solved.
 Small (P) is a Boolean-valued function which determines whether the input size is small enough
so that the answer can be computed without splitting.
 If this is true, function ‘S’ is invoked, otherwise, the problem ‘P’ is divided into smaller sub
problems.
 These sub problems P1, P2, . . . , Pk are solved by recursive application of DAndC.
 Combine () is a function which determines the solution to P using the solutions to the k-
subproblems.

c)

---------------------------------------------------------------------------------------------------------------------------------
7. a) What is recurrence relation?
b) What are the methods available to solve the recurrence relations?
c) Write the pseudo code or algorithm for binary search and time complexity in worst, average and
best case.
Answer:
a) Recurrence Relation: A recurrence relation is an equation that defines a sequence based on a rule that
gives the next term as a function of the previous term(s).
b) Methods to solve Recurrence Relations:

c) Algorithm for Binary Search:

Binary Search : Binary search is a process of searching an element in a sorted list (array) of
elements.
The Pseudocode for Binary search is:
1 Algorithm BinSearch (a, n, x)
2 //Given an array a[1:n ] of elements in nondecreasing
3 // order, n > 0, determine whether x is present, and
4 // if so, return j such that x:=a[j], else return 0.
5{
6 low : = 1;
7 high : = n;
8 while (low ≤ high) do
9 {
10 mid : =  ( low + high ) / 2  ;
11 if(x < a[mid]) then high:= mid - 1;
12 else if (x > a[mid]) then low:=mid + 1;
13 else return mid;
14 }
15 return 0;
16 }
Algorithm: Binary Search

 The time complexity of Binary search is :

-----------------------------------------------------------------------------------------------------------------------------
8. a) How to derive the recurrence relation of merge sort?
b) Write the pseudo code or algorithm of merge sort and time complexity.
c) 8,3,2,9,7,1,5,4  Apply merge sort and sort the elements.

Answer: Refer DAA PDF Notes or class notes; topic: Unit-I Part-II Merge sort

Questions: 9, 10 also can refer from DAA Notes/PDF notes.

 DAA UNIT-II

a. What is disjoint set?

1 b. Explain the weighted union and collapsing find.

a. What are the applications of disjoint set?

2 b. Explain the algorithm for simple union, weighted union, collapsing find.
a. What does the need of collapsing find?
b. Detect the cycle in the following graph using array
representation
3

a. Discuss the backtracking technique with an example

b. Detect the cycle in the following graph using array
4 representation

a. Detect the cycle in the following graph using array representation

5 b. In a class, there will be only one “three-seater”

bench is available. 2 boys and 1 girl must sit in that bench. Explain the
following using backtracking with state space tree
1. What are the possibilities of seating arrangements?
2. If “girl must not sit in between 2 boys” means, what are the possibilities?

a. Write the N queens algorithm or pseudo code

b. In the board, 4 queens already placed. The remaining 4 queens to be placed in
6 the board in which position? Explain how to be placed? (8 Queens Problem)
c. 7 5 3 1 ? ? ? ?
a. In the board, 4 queens already placed. The remaining 4 queens to be placed in
the board in which position? Explain how to be placed? (8 Queens Problem)
6 4 7 1 ? ? ? ?
7
b. Solve the sum of subset problem.
Given weights [1 to 6] = {5,10,12,13,15,18}. Sum of weights for subset (m)
should be 30.
a. Explain the Backtracking technique using state space tree with an example.
b. A tropical fish hobbyist has six different types of fish: A, B, C, D, E, and F.
Because of predator type relationships, water condition, and size, some of the
fish cannot be kept in the same tank. The following table show which fish
cannot be together:
8 Type A B C D E F
Cannot
B,C A,C,E A,B,D,E C,F B,C,F D,E
be with
What is the smallest number of tanks needed to keep all the fish? Using m-
coloring find the solution.
 a. GNIT is offering eight courses during summer session. The table shows with an
“X” which pairs of courses have one or more students in common. Only two air-
conditioned lecture halls are available for use at any one time.
Maths Eng Che Phy PPS EG EDC BEE
Maths X X X X X
Eng X X X
Che X X X
9 Phy X X
PPS X X
EG X X X X X
EDC X X
BEE X X X
Using m-coloring algorithm, design an efficient way to schedule the final
examinations.
b. What are the applications of disjoint set?
a. Detect the cycle in the following graph using array
representation
10 b. Solve the sum of subset problem.
Given weights [1 to 6] = {3,4,34,5,2,12}. Sum of
weights for subset (m) should be 9.

ANSWERS
Q1. a) What is disjoint set?
b) Explain the weighted union and collapsing find.
Answer:
a) Disjoint Set: If Si and Sj, i ≠ j, are two sets, then there is no element that is in both Si and Sj.

b) Weighted Union:
 To improve the performance of union and Find algorithms and avoiding the creation of
degenerate trees, the “Weighting rule for Union(i, j)” is used.
 Definition: If the number of nodes in tree with root “i” is less than the number of nodes in tree
root “j”, then make j the parent of i, otherwise make i the parent of j.
 When we use the weighting rule to perform the sequence of set unions given before, we obtain
the trees of below figure.

Figure: Trees obtained using the weighting rule

  The trees are obtained in above figure using the Weighting rule to perform the sequence of set
unions given before.
 In this figure, the unions have been modified so that the input parameter values correspond to the
roots of the trees to be combined.

Algorithm: Union algorithm with Weighting rule.

Collapsing Rule for Find:

 If ‘j’ is a node on the path from ‘i’ to its root and p[i] ≠ root[i], then set p[j] to root[i].

Algorithm: Find algorithm with Collapsing Rule

-----------------------------------------------------------------------------------------------------------------------------
Q 2. a) What are the applications of disjoint set?
b) Explain the algorithm for simple union, weighted union, collapsing find.
Answer:
a) Applications of Disjoint Set:
1) It is used to keep track of connected components in an undirected graph.
2) It is used to detect cycles in the graph.
3) It is used to calculate the minimum spanning tree in Kruskal's algorithm.
4) It is used in Maze generation problems.
5) Calculating mutual friends.
b) Answer:
i) Algorithm for Simple Union operation:
 To perform union, the SimpleUnion(i,j) function takes the inputs as the set roots i and j . And make
the parent of i as j i.e, make the second root as the parent of first root.
1 Algorithm SimpleUnion(i, j)
2{
3 p[i]:= j;
4}
Algorithm: Union operation
ii) Weighted Union & iii) Collapsing find: - Refer question number 1(b) [exclude weighted union example here]
-----------------------------------------------------------------------------------------------------------------------------
Q 3. a) What does the need of collapsing find?
b) Detect the cycle in the following graph using array representation.
Answer:
a) Collapsing Find:
 If ‘j’ is a node on the path from ‘i’ to its root and p[i] ≠ root[i], then set p[j] to
root[i].
 Collapsing find algorithm is used to perform find operation on the tree created by WeightedUnion.
b) Detecting the cycles in the given graph using Array representation:
 Consider the given graph:
 The above graph contains the 8 vertices. So, we represent all these 8 vertices in
a single array. Here, indices represent the 8 vertices. Each index contains a -1
value. The -1 value means the vertex is the parent of itself.

Now we will see that how we can represent the sets in an array.
 First, we consider the edge (1, 2). When we find 1 in an array, we observe that 1 is the parent of
itself. Similarly, vertex 2 is the parent of itself, so we make vertex 2 as the child of vertex 1. We add
1 at the index 2 as 2 is the child of 1. We add -2 at the index 1 where '-' sign that the vertex 1 is the
parent of itself and 2 represents the number of vertices in a set.

 The next edge is (3, 4). When we find 3 and 4 in array; we observe that both the vertices are parent
of itself. We make vertex 4 as the child of the vertex 3 so we add 3 at the index 4 in an array. We add
-2 at the index 3 shown as below:

 The next edge is (5, 6). When we find 5 and 6 in an array; we observe that both the
vertices are parent of itself. We make 6 as the child of the vertex 5 so we add 5 at the index 6 in an
array. We add -2 at the index 5 shown as below:
 The next edge is (7, 8). Since both the vertices are parent of itself, so we make vertex 8 as the child
of the vertex 7. We add 7 at the index 8 and -2 at the index 7 in an array shown as below:

 The next edge is (2, 4). The parent of the vertex 2 is 1 and the parent of the vertex 4 is 3. Since both
the vertices have different parent, so we make the vertex 3 as the child of vertex 1. We add 1 at the
index 3. We add -4 at the index 1 as it contains 4 vertices.
 Graphically, it can be represented as

 The next edge is ( 2,5 ). When we find vertex 2 in an array, we observe that 1 is the parent of the
vertex 2 and the vertex 1 is the parent of itself. When we find 5 in an array, we find -2 value which
means vertex 5 is the parent of itself. Now we have to decide whether the vertex 1 or vertex 5 would
become a parent. Since the weight of vertex 1, i.e., -4 is greater than the vertex of 5, i.e., -2, so when
we apply the union operation then the vertex 5 would become a child of the vertex 1 shown as
below:

 In an array, 1 would be added at the index 5 as the vertex 1 is now becomes a parent of vertex 5. We
add -6 at the index 1 as two more nodes are added to the node 1.

 The next edge is (1,3). When we find vertex 1 in an array, we observe that 1 is the parent of itself. When we
find 3 in an array, we observe that 1 is the parent of vertex 3. Therefore, the parent of both the vertices are
same; so, we can say that there is a formation of cycle if we include the edge (1,3).
 The next edge is (6,8). When we find vertex 6 in an array, we observe that vertex 5 is the parent of vertex 6
and vertex 1 is the parent of vertex 5. When we find 8 in an array, we observe that vertex 7 is the parent of the
vertex 8 and 7 is the parent of itself. Since the weight of vertex 1, i.e., -6 is greater than the vertex 7, i.e., -2, so
we make the vertex 7 as the child of the vertex and can be represented graphically as shown as below:
 We add 1 at the index 7 because 7 becomes a child of the vertex 1. We add -8 at the index 1 as the weight of
the graph now becomes 8.
  The last edge to be included is (5, 7). When we find vertex 5 in an array, we observe that vertex 1 is the parent
of the vertex 5. Similarly, when we find vertex 7 in an array, we observe that vertex 1 is the parent of vertex 7.
Therefore, we can say that the parent of both the vertices is same, i.e., 1. It means that the inclusion (5,7) edge
would form a cycle.
[See Sendil sir’s notes for more clarification; Filename: Unit 2 Disjoint sets].
-----------------------------------------------------------------------------------------------------------------------------
Q 4. a) Discuss the backtracking technique with an example
b) Detect the cycle in the following graph using array representation.
Answer:

a) Backtracking Technique:
 In solving some problems, a situation may arise where there are different ways leading from a
given position but unfortunately, none of them known to lead to a solution.
 After trying one path successfully, we return to the previous position and try to find a solution
using another path.
 However, we must ensure that, we must ensure that such a return is possible and all paths can be
tried. This technique is called “Backtracking”.
 Conceptually, a backtracking algorithm does a depth-first search of a tree of possible (partial)
solutions.
Example: Maze (a tour puzzle)
Given a maze, find a path from start to finish.
 In maze, at each intersection, you have to decide between 3 or fewer choices:
Go straight
Go left
Go right
 You don’t have enough information to choose correctly
 Each choice leads to another set of choices.
 One or more sequences of choices may or may not lead to a solution.
 Many types of maze problem can be solved with backtracking.
4 b) Answer:

[Write description accordingly with reference to previous question 3(b)]

-----------------------------------------------------------------------------------------------------------------------------
Q 5. a) Detect the cycle in the following graph using array
representation.
Answer: Refer 4(b) answer.
5. b) In a class, there will be only one “three-seater” bench is available. 2 boys and 1 girl must sit in
that bench. Explain the following using backtracking with state space tree
1. What are the possibilities of seating arrangements?
2. If “girl must not sit in between 2 boys” means, what are the possibilities?
Answer:

 Given that there is a three-seater bench, with two boys and a girl must sit on it.
 There are a total of 3! = 6 possibilities. We will try all the possibilities and get the possible solutions.
 Let B1, B2 and G be two boys and a girl respectively.

Figure: All the possible seating arrangements

1. The State-space tree for all the possibilities of seating arrangements are:

 The above state-space tree represents all the possible seating arrangements of the two boys and a
girl on a three-seater bench.
2. The possible State-space tree for “girl must not sit in between 2 boys”:
 Here the given constraint is that “The girl must not sit in between two boys”.

 In the above state-space tree, whenever G comes in between B1 & B2, there the further nodes get
killed, as it is a bounding function.

Q 6. a) Write the N queens algorithm or pseudo code.

b) In the board, 4 queens already placed. The remaining 4 queens to be placed in the board in
which position? Explain how to be placed? (8 Queens Problem)
7 5 3 1 ? ? ? ?
6. a) Answer:

Algorithm: All solutions to the n-queens problem

Algorithm: To check whether a new queen be placed.

[6(b) answer refer from sendil sir’s notes]
-----------------------------------------------------------------------------------------------------------------------------------------------

Q 7. a) In the board, 4 queens already placed. The remaining 4 queens to be placed in the board in
which position? Explain how to be placed? (8 Queens Problem)
6 4 7 1 ? ? ? ?
b) Solve the sum of subset problem.
Given weights [1 to 6] = {5,10,12,13,15,18}. Sum of weights for subset (m) should be 30.
Answer:
[for answer to Q7(a) refer sendil sir’s note; filename: “Unit 2 Backtracking upto subset”]
[for answer to Q7(b) refer my DAA PDF notes Unit-II Part-II, or your classnotes, topic: Sum of subsets
example problem.]
-----------------------------------------------------------------------------------------------------------------------------------------------
Q 8. a) Explain the Backtracking technique using state space tree with an example.
b) A tropical fish hobbyist has six different types of fish: A, B, C, D, E, and F.
Because of predator type relationships, water condition, and size, some of the fish cannot
be kept in the same tank. The following table show which fish cannot be together:
Type A B C D E F
Cannot
B,C A,C,E A,B,D,E C,F B,C,F D,E
be with

What is the smallest number of tanks needed to keep all the fish? Using m-coloring find the
solution.
Answer:
8. a) Backtracking:
 In solving some problems, a situation may arise where there are different ways leading from a
given position but unfortunately, none of them known to lead to a solution.
 After trying one path successfully, we return to the previous position and try to find a solution
using another path.
 However, we must ensure that, we must ensure that such a return is possible and all paths can be
tried. This technique is called “Backtracking”.

Algorithm: Recursive Backtracking algorithm

Explanation:
 The solution vector (xi, ..., xn) is treated as a global array x[l:n].
 All of the possible elements for the kth position of the tuple which satisfy Bk are generated, one
by one, and adjoined to the current vector (x1, ..., xk-1).
 Each time xk is attached a check is made to determine if a solution has been found. Then the
algorithm is recursively invoked.
 When the for loop is exited, no more values for xk exist and the current copy of Backtrack ends.
 The last unresolved call now resumes, namely the one which continues to examine the remaining
elements assuming only k – 2 values have been set.
 Note that this algorithm causes all solutions to be printed and assumes that tuples of various sizes
may make up a solution. If only a single solution is desired, then a flag can be added as a
parameter to indicate the first occurrence of success.
8 b) Answer:

[Add some description to this; just the graph is the answer, but need to explain a little bit]
-------------------------------------------------------------------------------------------------------------------------
Q 9. a) GNIT is offering eight courses during summer session. The table shows with an “X” which
pairs of courses have one or more students in common. Only two air-conditioned lecture halls are
available for use at any one time.
Maths Eng Che Phy PPS EG EDC BEE
Maths X X X X X
Eng X X X
Che X X X
Phy X X
PPS X X
EG X X X X X
EDC X X
BEE X X X
Using m-coloring algorithm, design an efficient way to schedule the final examinations.

b) What are the applications of disjoint set?

Answer:
9 b) Answer:
Applications of Disjoint Set:
1) It is used to keep track of connected components in an undirected graph.
2) It is used to detect cycles in the graph.
3) It is used to calculate the minimum spanning tree in Kruskal's algorithm.
4) It is used in Maze generation problems.
5) Calculating mutual friends.
-------------------------------------------------------------------------------------------------------------------------
Q 10. a) Detect the cycle in the following graph using array representation
b) Solve the sum of subset problem.
Given weights [1 to 6] = {3,4,34,5,2,12}. Sum of weights for subset (m)
should be 9.
Answer:
a) [Refer QNo. 4 (b) answer and refer classnotes for 10 (b) answer].
 DAA UNIT-III DYNAMIC PROGRAMMING
a. What is the need of dynamic programming? What are the different approaches
1 used in dynamic programming? Explain with an example.
a. Solve the following knapsack problem using tabulation method. Profit =
{11,21,31,33} W = {2,11,22,15} m = 40
b. Compute all pairs shortest path for the
following graph
2

a. Find the Optimal Binary Search Tree for the following keys
Obj 1 2 3 4
Keys 10 20 30 40
3 Frequency 4 2 6 3
b. Solve the following knapsack problem using set method.
Profit = {1,2,5,6} W = {2,3,4,5} m = 8
a. What is the need of dynamic programming? What are the different methods used
in dynamic programming? Explain with an example
4 b. Solve the following knapsack problem using set method.
Profit = {11,21,31,33} W = {2,11,22,15} m = 40
a. What is the need of dynamic programming? What are the different methods used
in dynamic programming? Explain with an example
b. Compute all pairs shortest path for the following graph
5

a. Discuss the memorization method used in dynamic programming.

b. Find the maximum reliability with minimum cost for the given data. Total cost is
105 $
6 Di Ci Ri
D1 30 0.9
D2 15 0.8
D3 20 0.5
a. Describe the traveling salesman problem.
b. Find the minimum cost tour for the following graph using dynamic programming.
Cost of the edges are given by the matrix shown
0 10 15 20
7 5 0 9 10
6 13 0 12
8 8 9 0

a. Discuss the iteration method used in dynamic programming.

8 b. Solve the following knapsack problem using tabulation method.
Profit = {1,2,5,6} W = {2,3,4,5} m = 8
a. Discuss the memorization method used in dynamic programming.
9 b. Solve the following knapsack problem using set method.
Profit = {1,2,5,6} W = {2,3,4,5} m = 8
a. Discuss the memorization method used in dynamic programming.
b. Find the Optimal Binary Search Tree for the following keys
10 Obj 1 2 3 4
Keys 10 20 30 40
Frequency 4 2 6 3
 UNIT-III ANSWERS
Q 1. What is the need of dynamic programming? What are the different approaches used in dynamic
programming? Explain with an example. [10 Marks]
Answer:
Dynamic Programming: Dynamic programming is an algorithmic design method that can be used when
the solution to a problem can be viewed as the result of a sequence of decisions.
 The basic idea of Dynamic programming is to store the result of a problem after solving it.
 So, when we get the need to use the solution of the problem then we don’t have to solve the problem
again and just use the stored solution.
 Example: One classic example of dynamic programming is the Fibonacci sequence. The Fibonacci
sequence is a series of numbers in which each number is the sum of the two preceding ones, starting
from 0 and 1.
 The formula for calculating the Fibonacci sequence is:

 To solve this problem using dynamic programming, we can create a table or array to store the solutions
to each subproblem.
 A simple algorithm for the Fibonacci sequence is given by:
Approaches Used in Dynamic Programming:
 There are two ways of implementing the dynamic programming, they are:
a) Memoization
b) Tabulation
a) Memoization:
 Memoization is a technique that is used to implement the DP algorithms.
 Memorization is also known as a top-down approach.
 It starts from solving the highest-level sub-problems. Initially, it solves the highest-level subproblem
and then solve the next sub-problem recursively and the next.
  Example: Memoization in Fibonacci sequence-

 It is very similar to our naïve implementation, but here we pass our function a “memo” argument and
initialize it as an array.
 Each time we recursively call Fibdown(), we pass it the memo array.
 If the value of memo[n] is undefined, meaning there’s no value stored in that index yet, we assign that
value the returned values of Fibdown (n - 1, memo) + Fibdown (n - 2, memo).
 b) Tabulation:
 Tabulation is a technique that is used to implement the DP algorithms.
 It is also known as a bottom-up approach (or) Iteration method.
 It starts from solving the lowest level sub-problem. The solution to the lowest level sub-problem
will help to solve next level sub-problem, and so forth.
 Example: Let us write the algorithm for the Fibonacci series using bottom-up approach:

 In above algorithm, an integer input “n” is provided and create an array for “F”.
 The F[] array is initialized for elements ‘0’ & ‘1’.
 Others elements of the Fibonacci series are stored in the array F[] using a for-loop.
 Finally, F[n] is returned.

 The loop is run as long as “i” is less than or equal to “n” to reach the nth value correctly. The loop
is iterated and “i” is incremented each time instead of recursively breaking down. This ensures
that no value is recomputed and the current value is returned in O(n) time.
---------------------------------------------------------------------------------------------------------------------------------
Q 2. a) Solve the following knapsack problem using tabulation method.
Profit = {11,21,31,33} W = {2,11,22,15} m = 40.
b) Compute all pairs shortest path for the following graph.

Answer: [For QNo. 2(a) refer sendil sir’s notes; filename: Unit 3 DP 0 1 Knapsack.pdf or
refer the website: https://www.javatpoint.com/0-1-knapsack-problem
[For QNo. 2(b) refer your DAA class notes]
---------------------------------------------------------------------------------------------------------------------------------
Q 3. a) Find the Optimal Binary Search Tree for the following keys
Obj 1 2 3 4
Keys 10 20 30 40
Frequency 4 2 6 3

b) Solve the following knapsack problem using set method. Profit = {1,2,5,6} W = {2,3,4,5} m = 8.
Answer: [Refer notes]
---------------------------------------------------------------------------------------------------------------------------------
Q 4. a) What is the need of dynamic programming?
What are the different methods used in dynamic programming? Explain with an example.
b) Solve the following knapsack problem using set method.
Profit = {11,21,31,33} W = {2,11,22,15} m = 40. [5+5 Mark]
4. a) Answer: [DP answer simplified here]
Dynamic Programming: Dynamic programming is an algorithmic design method that can be used when
the solution to a problem can be viewed as the result of a sequence of decisions.
 The basic idea of Dynamic programming is to store the result of a problem after solving it.
 So, when we get the need to use the solution of the problem then we don’t have to solve the problem
again and just use the stored solution.
Approaches Used in Dynamic Programming:
 There are two ways of implementing the dynamic programming, they are:
i) Memoization
ii) Tabulation
i) Memoization:
 Memoization is a technique that is used to implement the DP algorithms.
 Memorization is also known as a top-down approach.
 It starts from solving the highest-level sub-problems. Initially, it solves the highest-level subproblem
and then solve the next sub-problem recursively and the next.
 Example: Memoization in Fibonacci sequence-
 It is very similar to our naïve implementation, but here we pass our function a “memo” argument and
initialize it as an array.

ii) Tabulation:
 Tabulation is a technique that is used to implement the DP algorithms.
 It is also known as a bottom-up approach (or) Iteration method.
 It starts from solving the lowest level sub-problem. The solution to the lowest level sub-problem
will help to solve next level sub-problem, and so forth.
 Example: Let us write the algorithm for the Fibonacci series using bottom-up approach:

 In above algorithm, an integer input “n” is provided and create an array for “F”.
 The F[] array is initialized for elements ‘0’ & ‘1’.
 Others elements of the Fibonacci series are stored in the array F[] using a for-loop.
 Finally, F[n] is returned.
  The time complexity here, using tabulation method is reduced to O(n).

Q 4. b) Answer: [Refer DAA Classnotes-given as an exercise problem]

--------------------------------------------------------------------------------------------------------------------------------------------------

Q 5. a) What is the need of dynamic programming?

What are the different methods used in dynamic programming? Explain with an example
b) Compute all pairs shortest path for the following graph

Answer: [For QNo. 5(a) refer answer 4(a) and for QNo. 5(b) refer classnotes/need to solve]
--------------------------------------------------------------------------------------------------------------------------------------------------

Q 6. a) Discuss the memorization method used in dynamic programming.

b) Find the maximum reliability with minimum cost for the given data. Total cost is 105 $.

Answer: [Refer QNo. 4(a) topic: Memoization for QNo. 6(a) and for 6(b) problem, refer sendil sir’s notes]

Di Ci Ri
D1 30 0.9
D2 15 0.8
D3 20 0.5
--------------------------------------------------------------------------------------------------------------------------------------------------
Q 7. a) Describe the traveling salesman problem.
b) Find the minimum cost tour for the following graph using dynamic programming.
Cost of the edges are given by the matrix shown.
0 10 15 20
5 0 9 10
6 13 0 12
8 8 9 0
Answer:
a) Traveling Salesman Problem:
 Let G = (V, E) be a directed graph. The tour of G is a directed simple cycle that includes every vertex in
V.
 The cost of a tour is the sum of the cost of the edges on the tour.
 The traveling salesperson problem to find a tour of minimum cost.
b) [Refer this problem from Classnotes, also given in mid-ii]
--------------------------------------------------------------------------------------------------------------------------------------------------
Q 8. a) Discuss the iteration method used in dynamic programming.
b) Solve the following knapsack problem using tabulation method.
Profit = {1,2,5,6}, W = {2,3,4,5}, m = 8
Answer: [Refer QNo. 4(a) (ii) topic: tabulation for 8(a) answer and refer sendil sir notes for 8(b)]
--------------------------------------------------------------------------------------------------------------------------------------------------

Q 9. a) Discuss the memorization method used in dynamic programming.

b) Solve the following knapsack problem using set method.
Profit = {1,2,5,6} W = {2,3,4,5} m = 8.

Answer: [Refer QNo. 4(a) topic: Memoization for QNo. 9(a) answer, and for 9(b) problem refer your class
notes]
--------------------------------------------------------------------------------------------------------------------------------------------------

Q 10. a) Discuss the memorization method used in dynamic programming.

b) Find the Optimal Binary Search Tree for the following keys
Obj 1 2 3 4
Keys 10 20 30 40
Frequency 4 2 6 3
Answer: [Refer QNo. 4(a) topic: Memoization for QNo. 10(a) and for 9(b) answer, and for 10 (b) problem
refer Sendil sir’s notes].
--------------------------------------------------------------------------------------------------------------------------------------------------

END OF UNIT-III
 DAA UNIT-IV GREEDY METHOD
a. What is greedy method? Discuss
b. Write the control abstraction of greedy method
c. Find the optimal solution for the knapsack problem using greedy method where m=15
1 Obj 1 2 3 4 5 6 7
Profit 5 10 15 7 8 9 4
Weight 1 3 5 4 1 3 2

a. Discuss the greedy method.

b. Find the optimal solution for the knapsack problem using greedy method where m=20
2 Obj 1 2 3
Profit 25 24 15
Weight 18 15 10

a. What is the need of greedy method?

b. Solve the Job sequencing with deadline problem using greedy method
3 Jobs 1 2 3 4 5
Profit 20 15 10 5 1
Deadline 2 2 1 3 3

a. Discuss the Prim’s algorithm to find the minimum cost spanning tree
b. Apply the Prim’s algorithm and find the optimal solution
4

a. Discuss the Kruskal’s algorithm to find the minimum cost spanning

tree. What is the time complexity of Kruskal’s algorithm?
b. Apply the Kruskal’s algorithm and find the optimal solution
5

a. Explain the Prim’s algorithm. What is the time complexity of Prim’s

algorithm?
6 b. Apply the Prim’s algorithm and find the optimal solution

a. Write the pseudo code or algorithm for Dijkstra’s single shortest

path algorithm
7 b. Apply Dijkstra’s algorithm to find the shortest path of the given
graph

a. What is single source shortest path problem?

b. Apply Dijkstra’s algorithm to find the shortest path of the given graph
8

a. Discuss the greedy method.

b. Apply the Prim’s algorithm find the optimal solution
9

a. Discuss the greedy method

b. Solve the Job sequencing with deadline problem using greedy method
10 Jobs 1 2 3 4 5 6 7
Profit 35 30 25 20 15 12 5
Deadline 3 4 4 2 3 1 2
 DAA UNIT-IV ANSWERS
1. a) What is greedy method? Discuss.
b) Write the control abstraction of greedy method.
c) Find the optimal solution for the knapsack problem using greedy method where m=15
Obj 1 2 3 4 5 6 7
Profit 5 10 15 7 8 9 4
Weight 1 3 5 4 1 3 2
Answer:
1. a) Greedy Method:
 The greedy method is the most straight forward design technique, used to determine a feasible
solution that may or may not be optimal.
 A greedy algorithm obtains an optimal solution to a problem by making a sequence of choices.
For each decision point in the algorithm, the choice that seems best at the moment is chosen.
1. b) Control abstraction for greedy method:
 A control abstraction is a procedure whose flow of control is clear but whose primary operations are
specified by other procedures whose precise meanings are left undefined.

Algorithm: Greedy method control abstraction for the subset paradigm.

1. c) [Refer DAA class notes for this answer; topic: Unit-IV Greedy knapsack problem example]
--------------------------------------------------------------------------------------------------------------------------------------------------

2. a) Discuss the greedy method.

b) Find the optimal solution for the knapsack problem using greedy method where m=20
Obj 1 2 3
Profit 25 24 15
Weight 18 15 10
Answer:
2. a) [Refer QNo. 1(a) & (b) answers-needs to write both answers]
2. b) [Refer DAA class notes for this answer; topic: Unit-IV Greedy knapsack problem example]
--------------------------------------------------------------------------------------------------------------------------------------------------
Q 3. a) What is the need of greedy method?
b) Solve the Job sequencing with deadline problem using greedy method
Jobs 1 2 3 4 5
Profit 20 15 10 5 1
Dead line 2 2 1 3 3
3. a) Answer:
Greedy Method:
 Divide and conquer technique is applicable only for the problems which can be divisible.
 There exist some problems which cannot be divisible, which is the drawback of Divide-and-conquer
technique and this can be overcome in greedy method.
 The greedy method is the most straight forward design technique, used to determine a feasible
solution that may or may not be optimal.
 A greedy algorithm obtains an optimal solution to a problem by making a sequence of choices. For
each decision point in the algorithm, the choice that seems best at the moment is chosen.
3. b) Answer:
Job sequencing with deadline problem:
 Given a set of ‘n’ jobs. Associated with each Job i, has an integer deadline di  0 and a profit pi > 0.
 For any job ‘i’, the profit pi is earned iff the job is completed by its deadline.
Q 4. a) Discuss the Prim’s algorithm to find the minimum cost spanning tree.
b) Apply the Prim’s algorithm and find the optimal solution.

4. a) Answer:
Prim’s algorithm:
 Prim’s algorithm is a greedy method to obtain a minimum-cost spanning tree builds this tree edge-
by-edge. The next edge to include is chosen according to optimization criterion.
 The simplest such criterion is to choose an edge that results in a minimum increase in the sum of the
costs of the edges so far included.
The Prim’s Algorithm:

Algorithm: Prim’s minimum-cost spanning tree algorithm.

 The running time or time complexity for Prim’s algorithm is: O (n2).
4. b) Answer:
The given graph is:

[Write each step with explanation]

Q 5. a) Discuss the Kruskal’s algorithm to find the minimum cost spanning tree.
What is the time complexity of Kruskal’s algorithm?
b) Apply the Kruskal’s algorithm and find the optimal solution

5. a) Answer:
Kruskal’s algorithm:
 Kruskal’s algorithm is used to find the minimum-cost spanning tree.
 In Kruskal’s algorithm, the optimization criteria is that, the edges of the graph are considered in
non-decreasing order of costs.
 A set ‘t’ of edges so far selected to the spanning tree be such that it is possible to complete ‘t’ into a
tree. Thus ‘t’ may not be a tree at all stages.

Algorithm: Kruskal’s algorithm for constructing minimum-cost spanning tree.

 The time complexity of Kruskal’s algorithm is given by O(E log |V|) or O(E log n)
5. b) Apply the Kruskal’s algorithm and find the optimal solution.
Answer:
Given graph is:

[Write each step with explanation]

---------------------------------------------------------------------------------------------------------------------------------
Q 6. a) Explain the Prim’s algorithm. What is the time complexity of Prim’s algorithm?
b) Apply the Prim’s algorithm and find the optimal solution

6. a) Answer:
[Refer QNo. 4(a) for this answer]
6. b) Answer:
 The given graph is :

[Write explanation to each Step without fail]

Q 7. a) Write the pseudo code or algorithm for Dijkstra’s single shortest path algorithm
b) Apply Dijkstra’s algorithm to find the shortest path of the given graph
7. a) Answer:
Dijkstra’s Single Shortest Path algorithm:
 In Single-Source Shortest Path Problem, given a directed graph G = (V, E), a weighting function
‘cost’ for the edges of G, and a source vertex ‘v0’.
 The problem is to determine the shortest paths from v0 to all the remaining vertices of G.

Algorithm: Greedy algorithm to generate shortest paths.

 The time complexity of Single-source shortest path algorithm is O(n2).
7. b) Apply Dijkstra’s algorithm to find the shortest path of the given graph
Answer: The given graph is:

-----------------------------------------------------------------------------------------------------------------------------------------------------------
Q 8. a) What is single source shortest path problem?
b) Apply Dijkstra’s algorithm to find the shortest path of the given graph
Answer:
a) Single Source Shortest Path Problem:
 In Single-Source Shortest Path Problem, given a directed graph G = (V, E), a weighting function
‘cost’ for the edges of G, and a source vertex ‘v0’.

 The problem is to determine the shortest paths from v0 to all the remaining vertices of G.
 We can solve the shortest path problem, using a greedy algorithm developed by E. Dijkstra, that
generates the shortest paths in stages.
 In each stage, a shortest path to a new destination vertex is generated. The destination vertex for the
next shortest path is selected using the greedy criterion:
“From the vertices to which a shortest path has not been generated, select one that results in the
least path length”.
b) [Solve the problem just like QNo. 7(b) solution.]
-----------------------------------------------------------------------------------------------------------------------------------------------------

Q 9. a) Discuss the greedy method.

b) Apply the Prim’s algorithm find the optimal solution.
Answer:
a) [Refer QNo. 1(a) & (b) answers-both need to write]
b) [Refer QNo. 6 (b) answer]
-----------------------------------------------------------------------------------------------------------------------------------------------------

Q 10. a) Discuss the greedy method

b) Solve the Job sequencing with deadline problem using greedy method
Jobs 1 2 3 4 5 6 7
Profit 35 30 25 20 15 12 5

Answer: Dead line 3 4 4 2 3 1 2

a) [Refer QNo. 1(a) & (b) answers-both need to write]

b) [Refer DAA class notes and solve this problem; topic: Unit-IV Job sequencing with deadlines problem
example].

-----------------------------------------------------------------------------------------------------------------------------------------------------

END OF UNIT-IV
 UNIT-V
a. Discuss the branch and bound technique
1 b. Apply LCBB and find the shortest path

a. What is LCBB method?

b. Apply LCBB to solve the knapsack problem where m=15
2 Obj 1 2 3 4
Profit 10 10 12 18
Weight 2 4 6 9
a. Apply FIFOBB to solve the knapsack problem where m=15
Obj 1 2 3 4
3 Profit 10 10 12 18
Weight 2 4 6 9
a. What is P and NP? Discuss.
4
b. Explain the non-deterministic sorting algorithm.
a. Discuss the cook’s theorem
5
b. Discuss the 3 CNF Satisfiability problem
a. Discuss NP-Hard and NP-Complete
6
b. Discuss the Cook’s theorem
a. Discuss the non-deterministic algorithms
7
b. Discuss the branch and bound technique.
Apply LCBB to solve the knapsack problem where m=60
Obj 1 2 3 4 5
8 Profit 30 40 45 77 90
Weight 5 10 15 22 25
a. Apply FIFOBB to solve the knapsack problem where m=7
Obj 1 2 3
9 Profit 6 5 4
Weight 5 4 3
b. What is NP-Hard and NP-complete?
10 Explain the branch and bound technique with an example

ANSWERS
1. a) Discuss the branch and bound technique.
b) Apply LCBB and find the shortest path.