GURU NANAK INSTITUTE OF TECHNOLOGY

(A UGC Autonomous Institution – Affiliated to JNTUH)

Ibrahimpatnam, Ranga Reddy (District) - 501 506.

DESIGN AND ANALYSIS OF ALGORITHMS (22PC0CS08)

UNIT-I
Short Answer Questions
1 Define an algorithm.
2 List the two major phases of performance evaluation.
3 What do you mean by space and time complexity?
4 What is frequency count?
5 Define order of growth.
6 What is the difference between little o and big O?
7 What is the use of divide and conquer method?
8 What is the time and space complexity of quick sort?
9 What is the recurrence relation of merge sort?
10 Give the formula for Strassen’s matrix multiplication.

Answers
1. Define an algorithm.
Ans: An algorithm is a finite set of instructions which, if followed, accomplish a particular task.

2. List the two major phases of performance evaluation.

Ans: The two major phases of performance evaluation are: i) Time complexity and ii) Space
complexity.

3. What do you mean by space and time complexity?

Ans:
i) Space Complexity: The Space complexity of an algorithm is the amount of memory it needs to
run to its completion.
ii) Time Complexity: The time complexity of an algorithm is the amount of computer time it needs
to run to its completion.

4. What is Frequency count?

Ans: Frequency count:
 Frequency count specifies the number of times a statement is to be executed. So how many
times the statement within our algorithm is executed is known as Frequency count.
 [ Frequency count is a count denoting no. of times a statement is executing. ]
 Using Frequency count, we can able to find or calculate the time complexity for any algorithm.
5. Define order of growth.
Ans: Order of` Growth:
 An order of growth is a set of functions whose asymptotic growth behaviour is considered
equivalent. For example, 2n, 100n and n + 1 belong to the same order of growth, which is
written O(n) in Big-Oh notation and often called linear because every function in the set grows
linearly with n.

6. What is the difference between little o and big O?

Ans: Little oh notation (o) :
 The function f(n) = o(g(n)) if and only if for all n, n ≥ 0 .
Big Oh notation (O) :
 The function f(n) = O(g(n)) [read as "f of n is big-oh of g of n"] if and only if there exist
positive constant c and n0 such that f ( n )  c * g(n) for all n, n  n0 .

7. What is the use of divide and conquer method?

Ans: Divide and Conquer:
 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.

8. What is the time and space complexity of quick sort?

Ans: The time complexity of Quick sort is

 The Space complexity of Quick sort is O(log n).

9. What is the recurrence relation of merge sort?

Ans:
10. Give the formula for Strassen’s matrix multiplication.
Ans: The recurrence formula for Strassen’s matrix multiplication is given by:
 LONG-ANSWER QUESTIONS AND ANSWERS KEY
UNIT-I
Bloom’s
Q.
Unit No Question Taxonomy
No
Level
a) Differentiate between algorithm and pseudocode.
1 b) Write the procedure to be followed to convert a problem into L2
pseudocode with an example.
a) Discuss algorithm and its criteria.
b) Develop an algorithm to determine the minimum and maximum
L2
2 values in an array a[1: n] of integers n 1 and entries in the array
L3
used need not be distinct. Determine the worst-case complexity
function for the algorithm.
a) Illustrate how time complexity is calculated for the algorithms. L2
3
b) Write a recursive algorithm to find the factorial of a number. L3
4 Explain asymptotic notations with neat sketch. L2
a) Discuss the Master’s method.
b) Solve the récurrence relations : L2
5
Unit 1 i) T(n) = 2T(n/2) + cn and L3
ii) T(n) = 2T(n/2) + nlogn with T(1) = 1.
a) Explain control abstraction for divide and conquer method. L2
6
b) Write an algorithm to find sum of n-numbers. L3
a) Solve the recurrence relation using backward substitution L3
7 method: T(n) = 2T(n/2) + n with T(1)=1.
b) Derive the time complexity of binary search in worst case. L3
a) Explain Merge sort with algorithm. L2
8
b) Apply merge sort and sort the elements: 8,3,2,9,7,1,5,4 L3
9 Write pseudocode to sort the elements using quick sort. L2
a) Explain binary search algorithm.
L2
10 b) Sort the elements using binary search with key=60;
L3
10, 20, 30, 40, 50, 60.
 UNIT-I LONG ANSWERS KEY
1. a) Differentiate between algorithm and pseudocode.
b) Write the procedure to be followed to convert a problem into pseudocode with an example.
a) Ans:
Sno. Algorithm Pseudocode

It is defined as a sequence of well-defined

It can be understood as one of the methods that
1. steps. These steps provide a solution/ a way to
helps in the representation of an algorithm.
solve a problem in hand.

It is a systematic, and a logical approach, It is a simpler version of coding in a programming

2.
where the procedure is defined step-wise language.

It is written in plain English, and uses short

Algorithms can be represented using natural
3. phrases to write the functionalities that s specific
language, flowchart and so on.
line of code would do.

This solution would be translated to machine There is no specific syntax which is actually
4. code, which is then executed by the system to present in other programming languages. This
give the relevant output. means it can't be executed on a computer.

Many simple operations are combined to help

There are many formats that could be used to write
5. form a more complicated operation, which is
pseudo-codes.
performed with ease by the computer

Most of these formats take the structure from

6. It gives the solution to a specific problem.
languages such as C, LIST, FORTRAN, and so on.

It can be understood as the pseudocode for a Pseudocode is not actually a programming

7.
program. language.

Control structures such as 'while', 'if-thenelse',

8. Plain text is used.
'repeat-until', and so on can be used.

There are no rules to follow while constructing

9. It has certain rules to follow while constructing it.
it.

1. b) Write the procedure to be followed to convert a problem into pseudocode with an example.
Ans: Procedure to be followed for 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 an algorithm to find sum of n numbers.
Pseudocode: 1 Algorithm sum(n)
2 {
3 res: = 0.0;
4 for i:=1 to n do
5 res:= res + i;
6 return res;
7 }
Algorithm: Pseudocode to find sum of n-numbers

--------------------------------------------------------------------------------------------------------------------------------------------------------
2. a) Discuss algorithm and its criteria.
b) Develop an algorithm to determine the minimum and maximum values in an array a[1: n] of
integers n 1 and entries in the array used need not be distinct. Determine the worst-case
complexity function for the algorithm.
Ans: Algorithm:
 An algorithm is a finite set of instructions that, if followed, accomplish a particular task.

Figure: Notion of Algorithm

 The word algorithm comes from the name of a Persian author, Abu Ja’far Mohammed ibn
Musa al-Khwarizmi (c. 825 A.D.), who wrote a textbook on mathematics.
Criteria or Characteristics of an algorithm are:
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.
2. b) Develop an algorithm to determine the minimum and maximum values in an array a[1: n] of
integers n 1 and entries in the array used need not be distinct. Determine the worst-case
complexity function for the algorithm.
Ans:
Algorithm MinMax (a, n)
{
min:=a[1]; -------------------------------------------------------------------- 1
max:=a[1]; --------------------------------------------------------------------- 1
for i:=1 to n do --------------------------------------------------------------------- n+1
{
if a[i]  min then --------------------------------------------------------------------- n
min:= a[i]; --------------------------------------------------------------------- 1
if (a[i]  max then --------------------------------------------------------------------- n
max:=a[i]; --------------------------------------------------------------------- 1
}
write(“The minimum element is” +min); --------------------------------------------- 1
write(“The maximum element is” +max); --------------------------------------------- 1
}
----------------------------------------------------------------------------------------------------------------------------------
Algorithm: Finding minimum and maximum elements in an array Total Steps: 3 n + 7
----------------------------
 By eliminating constants and coefficients from the total steps, we can write the worst-case
complexity function is given as T(n) = O (n)
----------------------------------------------------------------------------------------------------------------------------- --------
3. a) Illustrate how time complexity is calculated for the algorithms.
b) Write a recursive algorithm to find the factorial of a number.
Ans:
3. a) Time Complexity :
 The time complexity of an algorithm is the amount of computer time it needs to run to completion.
 The time T(p) taken by a program P is the sum of the compile time and the run time(execution time),
i.e.,
T(P) = c + tp

where c is the compile time and tp is the run time of an program.

 The compile time does not depend on the instance characteristics.
 Also, we may assume that a compiled program will be run several times without recompilation .
 This run time is denoted by tp (instance characteristics).
  The value of tp (n) for any given n can be obtained only experimentally.
 The program is typed, compiled and run on any particular machine.
 The execution time is “physically clocked” and tp (n) obtained. Even with this experimental approach,
one could face difficulties.
 That means, it is difficult to compute the time complexity in terms of physically clocked time.
 The time complexity is therefore given in terms of “Frequency count”.
 Frequency count is a count denoting no. of times a statement is executing.
Approaches to Time Complexity: There are two approaches to measure the time complexity of an
algorithm:
i) Priori Analysis - In this, before executing an algorithm, we will analyze the behavior of the algorithm.
ii) Posteriori Analysis – In this, while executing the algorithm, we measure the execution time.

3. b) Recursive algorithm:

Algorithm RFactorial ( n )
// n is the number to be given as input
{
if ( n ≤ 1 ) then
return 1;
else
return n*RFactorial (n-1);
}
-------------------------------------------------
Algorithm: finding factorial of a number

----------------------------------------------------------------------------------------------------------------------------- --------
4. Explain asymptotic notations with neat sketch.
Ans: 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.
 Asymptotic notations are the mathematical notations used to describe the running time of an algorithm
when the input tends towards a particular value or a limiting value.
 Asymptotic Notation is used to describe the running time of an algorithm - how much time an
algorithm takes with a given input, n.
 Asymptotic notations are the shorthand way to represent time complexity.
 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 an
algorithm. Thus, it gives the worst-case complexity of an algorithm.
n
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 c 1
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 for all n, n ≥ 0 .
5. Little omega notation ( ω ) :
 The function f(n)= ω (g(n)) if and only if for all n, n ≥ 0 .
----------------------------------------------------------------------------------------------------------------------------- --------
5. a) Discuss the Master’s method.
b) Solve the recurrence relations :
i) T(n) = 2T(n/2) + cn and
ii) T(n) = 2T(n/2) + nlogn with T(1) = 1.
Solution:
5. a) Master’s Theorem/Method:
Any recurrence relation can be solved using Master’s method with the following steps:
Step 1: Compare the given equation with T(n) = aT(n/b) + f(n)
𝒇(𝒏)
Step 2: Take h(n) =
𝒏𝐥𝐨𝐠 𝒃 𝒂
 Step 3: Find u(n) using the following table:

h(n) u(n)

O(nr), r<0 O(1)

(𝒍𝒐𝒈𝒏 )𝒊+𝟏
θ((logn)i), i  0 θ
𝒊+𝟏

(nr), r>0 θ (h(n))

Step 4: Solve T(n) using the formula:

T(n) = 𝑛log𝑏 𝑎 [ T(1) + u(n) ]

5. b) Solve the recurrence relations :

i) T(n) = 2T(n/2) + cn and
ii) T(n) = 2T(n/2) + nlogn with T(1) = 1.
Solution:
i) T(n) = 2T(n/2) + cn with T(1)=1.
ii) T(n) = 2T(n/2) + nlogn with T(1) = 1.
Solution:
6. a) Explain control abstraction for divide and conquer method.
b) Write an algorithm to find sum of n-numbers.
Answer:
6. 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.
Control abstraction for 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.
6. b) Algorithm to find sum of n-numbers:
1 Algorithm sum(a, n)
2 {
3 res: = 0.0;
4 for i:=1 to n do
5 res:= res + i;
6 return res;
7 }
Algorithm: Pseudocode to find sum of n-numbers

----------------------------------------------------------------------------------------------------------------------------- -----
7. a) Solve the recurrence relation using backward substitution method: T(n) = 2T(n/2) + n with T(1)=1.
b) Derive the time complexity of binary search in worst case.
7. a) Solution: (also you can refer class notes)
 [∵ T(1) = 1]
 Therefore, T(n) = 𝑛 + 𝑛𝑙𝑜𝑔2𝑛
 By eliminating smaller inputs from above equation, the time complexity is given as

T(n) = O (𝑛𝑙𝑜𝑔2𝑛 )

7. b) Derive the time complexity of binary search in worst case.

Ans: Solving Worst case efficiency for Binary Search:
 The worst-case efficiency in binary search occurs when the desired element (key) is not present in the
given array list. So, the binary search algorithm continues to divide the array every time, into exactly
half, until there is only one element left to check.
 Here, we divide the array into two halves in time T (n/2) and one comparison is made with the middle
element and hence the worst-case recurrence equation is given by:

1 when n  1

T(n) =
𝑛
T ( ) + 1, otherwise
2

𝑛
 Consider T (n) = T ( ) + 1 ------------ equation 1
2
 Solve the above eq. 1 using backward substitution method, we get
 Therefore, the binary search time complexity in worst case is T (n) = O (𝑙𝑜𝑔2𝑛 )

[You can refer notes also for the derivation]

----------------------------------------------------------------------------------------------------------------------------- -----
8. a) Explain Merge sort with algorithm.
b) Apply merge sort and sort the elements: 8, 3, 2, 9, 7, 1, 5, 4
Ans:
a) Merge Sort :
 Sorting is a process of arranging the list of elements either in ascending or descending order.
 Merge sort is a sorting algorithm which works on Divide and Conquer principle.
 The steps forwarded in Merge sort are:
1. Merge sort works by dividing the given array into two subarrays of equal size.
2. The subarrays are sorted independently using recursion.
3. The sorted subarrays are then merged to get the solution for the original array.
4. In this algorithm,
˗ breaking of the given input array into two subarrays of equal size is a part of “divide” step.
˗ The recursive calls to sort the subarrays are part of the “conquer” step.
˗ The merging of subarrays to get the solution for the original array is a part of the “combine”
step.
 Algorithm: Merge Sort

Algorithm: Merging two sorted subarrays using auxiliary storage

8. b) Apply merge sort and sort the elements: 8, 3, 2, 9, 7, 1, 5, 4
Ans: Consider the given array of elements:
Position:
1 2 3 4 5 6 7 8

8 3 2 9 7 1 5 4
Elements:

8 3 2 9 7 1 5 4 Divide

8 3 2 9 7 1 5 4

8 3 2 9 7 1 5 4

Conquer
3 8 2 9 1 7 4 5

2 3 8 9 1 4 5 7 Merge/Combine

1 2 3 4 5 7 8 9

------------------------------------------------------------------------------------------
Figure: Merge sort

----------------------------------------------------------------------------------------------------------------------------- -----
9. Write pseudocode to sort the elements using quick sort.
Ans:

Algorithm: Sorting by partitioning

 Algorithm: Partition the array a[m:p-1] about a[m]

 The Time complexity of Quick Sort is:

----------------------------------------------------------------------------------------------------------------------------- -----
10. a) Explain binary search algorithm.
b) Sort the elements using binary search with key=60;
10, 20, 30, 40, 50, 60.

Ans:
10. a) 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: Iterative Binary Search

 The time complexity of Binary search is :

(or)

(any one of the tables from above write in exam)

10. b) Binary search Example:

Ans:
----------------------------------------------------------------------------------------------------------------------------- -----
*** END OF UNIT-I ***
 UNIT-II LONG ANSWERS
a) Describe disjoint sets with its various representations.
1
b) Write Simple union and find algorithms.
a) Explain weighting rule for union with example.
2 b) Write a short note on: i) Explicit constraints and
ii) Implicit constraints

3 Elaborate the need of collapsing find with an algorithm.

a) Discuss the backtracking technique.

4
b) Explain the constraints that are used to solve any problem using backtracking.

a) Give the strategy to represent the solution vector for 4-Queens problem with
neat sketch.
b) In a class, there will be only one “three-seater” bench is available. 2 boys and
5 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) Explain n-queens problem with algorithm.
6
b) Draw the complete/full state-space tree for the 4-queens problem.
a) Solve the sum of subset problem:
b) Given weights w[1:6] = {5, 10, 12, 13, 15, 18}. Sum of weights for subset (m)
7
should be 30. Draw the portion of state-state space tree that is generated using
SumOfSubsets algorithm.
a) Explain recursive backtracking algorithm.
8 b) Write a short note on:
i) Live node ii) E-node iii) Dead node
a) Discuss Graph-coloring problem.
b) Draw a state-space tree for the below 4-node graph for m-
colorability problem.
9
c) Two sets S1 and S2 are given as S1={1, 2, 4, 6} and S2 = {7, 8}.
i) Draw disjoint sets for S1 and S2 using trees.
ii) Draw disjoint set S3 using trees such that S3=S1 U S2.
a) Explain sum of subsets problem with algorithm.
10 b) Draw three graphs, among which, two graphs must have Hamiltonian cycle
and one cannot have it.
 UNIT-II LONG ANSWERS KEY
1. a) Describe disjoint sets with its various representations.
b) Write Simple union and find algorithms.
Ans:
1. a) Disjoint Set:
 If Si and Sj, i ≠ j are two sets, then there is no element that is in both Si and Sj.
 Various Representations of Disjoint sets are:
1. Tree Representation
2. Data Representation
3. Array Representation
 Example: Let n = 10 elements can be partitioned into three disjoint sets as follows:
S1 = { 1, 7, 8, 9 }, S2 = { 2, 5, 10 } and S3 = { 3, 4, 6 }
1. Tree Representation:
The Tree Representations for these disjoints are:

--------------------------------------------------------------------------------------------------
Figure: Possible Tree representations for the disjoint sets S1, S2, S3
2. Data Representation:
 To perform Union or Find operations efficiently on sets, it is necessary to represent the set
elements in a proper manner.
 The data representation for S1, S2, S3 take the following form:

Figure: Data Representation of Disjoint sets

  If we wish to unite Si and Sj then we need to unite the trees with roots FindPointer(S i) and

FindPointer(Sj).
 Here “FindPointer” is a function that takes a set name and determines the root of the tree that
represents it.
 This is done by an examination of the “[setname, pointer]” table.
 In many applications, the “setname” is just the element at the root.
 The Find(i) operation now becomes:
˗ Determine the root of the tree containing element “i”.
3. Array Representation:
 Since the set elements are numbered 1 through n, we represent the tree nodes using an array
p[1:n], where n is the maximum no. of elements.
 The ith element of this array represents the tree node that contains element i.
 This array element gives the parent pointer of the corresponding tree node.
 The below figure shows the array representation of the sets S1, S2 and S3 of above tree
representation.
 The root nodes have a parent of -1.

Figure: Array Representation of sets

1. b) Write Simple union and find algorithms.
Ans: 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.

Algorithm :
----------------------------------------------------------------------------------------------------------------------------- -----
2. a) Explain weighting rule for union with example.
b) Write a short note on: i) Explicit constraints and ii) Implicit constraints.
Ans:
2. a) 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.

2. b) Write a short note on: i) Explicit constraints and ii) Implicit constraints.
Ans: i) Explicit constraints:
 Explicit constraints are the rules that restrict each xi to take on values only from a given set.
Examples:
i) xi ≥ 0 or si={all non-negative real numbers}
ii) Xi=0 or 1 or Si={0, 1}
iii) li ≤ xi ≤ ui or si={a: li ≤ a ≤ ui }
ii) Implicit constraints:
 Implicit constraints are the rules that determine which of the tuples in the solution space of
Instance characteristics I satisfy the criterion function.
 Thus implicit constraints describe the way in which the xi must relate to each other.
Example:
The implicit constraint for n-queens problem is that no two queens can be on the same row, same
column or same diagonal.
----------------------------------------------------------------------------------------------------------------------------- -----
3. Elaborate the need of collapsing find with an algorithm.
Ans: 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 trees created by WeightedUnion.

Algorithm: Find algorithm with Collapsing Rule

Collapsing Find Example (Can also write from DAA Notes)

----------------------------------------------------------------------------------------------------------------------------- -----
4. a) Discuss the backtracking technique.
b) Explain the constraints that are used to solve any problem using backtracking.
Ans:
4 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 B k 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.
4. b) Explain the constraints that are used to solve any problem using backtracking.
Ans: Backtracking is a Depth-First Search (DFS) with a bounding function known to be criterion function.
 Criterion Function: It is a function P(x1, x2, … , xn) which needs to be maximized or minimized for a
given problem.
 Many problems while solving by backtracking are required to satisfy a complexity set of constraints.
 For any problem, these constraints are categorized into two types: Explicit and Implicit constraints.
Explicit constraints:
 Explicit constraints are the rules that restrict each xi to take on values only from a given set.
Common Examples:
iv) xi ≥ 0 or si={all non-negative real numbers}
v) Xi=0 or 1 or Si={0, 1}
vi) li ≤ xi ≤ ui or si={a: li ≤ a ≤ ui }
 Explicit constraints depend on a particular instance I of the problem being solved.
 All tuples that satisfy the explicit constraints define a possible “solution space” for I.
ii) Implicit constraints:
 Implicit constraints are the rules that determine which of the tuples in the solution space of
Instance characteristics I satisfy the criterion function.
 Thus implicit constraints describe the way in which the xi must relate to each other.
Example:
The implicit constraint for n-queens problem is that no two queens can be on the same row, same
column or same diagonal.
----------------------------------------------------------------------------------------------------------------------------- -----
5. a) Give the strategy to represent the solution vector for 4-Queens problem with neat sketch.
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?
Ans:
5. a) 4-Queens Problem:
 Consider a 4x4 chessboard. Let there be 4-queens.
 The objective is to place these 4-queens on a 4x4 chessboard in such a way that no two queens should be
placed in the same row, same column or same diagonal positions.
 The explicit constraints are 4-queens have to be placed on 4x4 chessboard.
 The implicit constraint is that – no two queens are to be placed in the same row, same column or diagonal.
Solving 4-queens problem:
 Consider 4-queens and a 4x4 chessboard.
 Let (x1, x2, x3, x4) be the solution vector, where xi – column on which the queen-I must be placed.
 Start with an empty chessboard and place first queen in first row and first column.

 The second queen Q2 should not be placed in 1 st row and 2nd column. But it can be placed in 2 nd
row and, in third or fourth columns.
If we place in 2nd column, Q1 and Q2 will be in same diagonal, so let us place in 3 rd column.

 We cannot place the third queen Q3 in 3rd row, so we should go back to second queen and place it in 4th
column.
 The third queen now, can be placed in second column.

 Now, the fourth queen Q4 cannot be placed in fourth row. So, trace back and try to change the position of
Q3.

 So, go back to second row and try to change the position of Q2. But Q2 is already in last column, and
cannot move further. So, backtrack to Q1 and change the position of first queen Q1 to second column.

 In above figure, we placed the remaining queens-Q2, Q3 & Q4 in their appropriate positions.
 Hence the solution vector for the 4-Queen’s problem is (x1, x2, x3, x4) = (2, 4, 1, 3).
[which means that Q1 is placed in 2nd column, Q2 in 4th column, Q3 in 1st column and Q4 is placed in
3rd column].
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 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

i) 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.
ii) 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.
6. a) Explain n-queens problem with algorithm.
b) Draw the complete/full state-space tree for the 4-queens problem.

6. a) Answer:
n-queens Problem:
 Given n-queens and a nxn chessboard.
 The objective is to place these n-queens on a nxn chessboard in such a way that no two queens should be
placed in the same row, same column or same diagonal positions.
 The explicit constraints are n-queens have to be placed on nxn chessboard.
 The implicit constraint is that – no two queens are to be placed in the same row, same column or diagonal.

Algorithm: All solutions to the n-queens problem

Algorithm: To check whether a new queen be placed.

6. b) Draw the complete/full state-space tree for the 4-queens problem.
Ans: State-Space Tree for 4-Queens problem:
 The following figure shows the complete state-space tree for the 4-queens problem.

Figure: Tree organization of the 4-queens solution space.

Nodes are numbered as in Depth-first search manner.
----------------------------------------------------------------------------------------------------------------------------- ------
7. Solve the sum of subset problem: Given weights w[1:6] = {5, 10, 12, 13, 15, 18}. Sum of weights for subset
(m) should be 30. Draw the portion of state-state space tree that is generated using SumOfSubsets
algorithm.
Solution: Given that, no. of objects, n=6
The given weights are w1=5, w2=10, w3=12, w4=13, w5=15, and w6=18 and
the total weight, m=30.
Let us initialize, Sum (S) = 0,
Index (k) = 1 and
the remaining sum (r) = 73 [sum of given weights:5+10+12+13+15+18]
The state-space tree for the given sum of subsets problem is given as follows:
 Figure: Portion of State-space tree that is generated using SumOfSubsets algorithm

 In above figure, the rectangular nodes list the values of S, k, and r.

 Circular nodes represent a point at which subsets with sum ‘m’ are printed out.
 At nodes A, B, and C, the output is respectively given as
(1, 1, 0, 0, 1), (1,0, 1, 1) and (0, 0, 1, 0, 0, 1)
----------------------------------------------------------------------------------------------------------------------------- -----
8. a) Explain recursive backtracking algorithm.
b) Write a short note on:
i) Live node ii) E-node iii) Dead node
8. a) Recursive Backtracking algorithm:
Ans: 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 B k 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.
8. b) Write a short note on:
i) Live node ii) E-node iii) Dead node
Ans: i) Live node: Live node is a node that has been generated but whose children have not yet been
generated.
ii) E-node: The live node whose children are currently being generated is called the E-node (node being
expanded).
iii) Dead node: It is generated node that is either not to be expanded further or one for which all of its
children have been generated.
9. a) Discuss Graph-coloring problem.
b) Draw a state-space tree for the below 4-node graph for m-colorability problem.
c) Two sets S1 and S2 are given as S1={1, 2, 4, 6} and S2 = {7, 8}.
i) Draw disjoint sets for S1 and S2 using trees.
ii) Draw disjoint set S3 using trees such that S3=S1 U S2.

9. a) Graph-coloring problem:
Ans:
 Let G be an undirected graph and ‘m’ be a given positive integer.
 The graph coloring problem is assigning colors to the vertices of an undirected graph with the restriction
that no two adjacent vertices are assigned the same color yet only ‘m’ colors are used.
 The optimization version calls for coloring a graph using the minimum number of colorings.
 The decision version, known as m-coloring asks whether a graph is colourable using at most m-colors.
 Note that, if ‘d’ is the degree of the given graph then it can be colored with ‘d+1’ colors.
 The m-colorability optimization problem asks for the smallest integer ‘m’ for which the graph G can be
colored. This integer is referred as “Chromatic number” of the graph.
9. b) State-space tree for the given 4-node graph is:
Ans: Given graph:

The state-space tree for the above graph is:

Figure:
9. c) Two sets S1 and S2 are given as S1={1, 2, 4, 6} and S2 = {7, 8}.
i) Draw disjoint sets for S1 and S2 using trees.
ii) Draw disjoint set S3 using trees such that S3=S1 U S2.
Solution: Given two disjoint sets S1={1, 2, 4, 6} and S2 = {7, 8}.
i) The possible tree representation for the disjoint sets S1 and S2 is:

S1 S2

ii) The possible tree representation for S3 = S1 U S2 is given as:

S3 = S1 U S2

----------------------------------------------------------------------------------------------------------------------------
10. a) Explain sum of subsets problem with algorithm.
b) Draw three graphs, among which, two graphs must have Hamiltonian cycle and one cannot have it.

10. a) Ans:
Sum of Subsets Problem:
 Given n-distinct positive numbers, usually called weights, wi, 1 ≤ i ≤ n, and m, this problem requires for
finding all subsets of wi whose sums are ‘m’.

 The Explicit constraints are xi { j | j is an integer and 1 ≤ j ≤ n }.

 The implicit constraints require that no two xi be the same and that the sum of the corresponding wi ‘s
be “m”.
 To avoid generating multiple instances of the same subset (for instance, (1, 2, 4) and (1, 4, 2) represent
the same subset). So another implicit constraint that is imposed is that xi < xi+1, 1 ≤ i ≤ n.
Algorithm: Recursive backtracking algorithm for Sum of Subsets problem.
----------------------------------------------------------------------------------------------------------------------------------------------

10. b) Draw three graphs, among which, two graphs must have Hamiltonian cycle and one cannot have
it.

Ans:

The Hamiltonian Cycles are:

1 – 3 – 4 – 5 – 6 – 7 – 8 – 2 – 1 and
1–2–8–7–6–5–4–3–1

The Hamiltonian Cycles are:

1 – 3 – 5 – 2 – 4 - 1 and
1–4–2–5–3-1

No Hamiltonian Cycle

End of Unit-II