CS1401- Design and Analysis of Algorithms Department of CSE, IT, ADS and AML 2023-2024

INTRODUCTION
Algorithm – Fundamentals of Algorithmic Problem Solving – Important Problem Types – The
Analysis Framework – Asymptotic Notations and Basic Efficiency Classes – Mathematical
Analysis of Non recursive and Recursive Algorithms – Empirical Analysis of Algorithms.
UNIT-I / PART-A
1. Define Algorithm. List the criteria of an algorithm or characteristics of an algorithm.
An algorithm is a sequence of unambiguous instructions for solving a problem,
i.e., for obtaining a required output for any legitimate input in a finite amount of time.
All algorithms must satisfy the following criteria
 Input: An algorithm should have some inputs
 Output: At least one output should be returned by the algorithm after the
completion of the specific task based on the given inputs
 Definiteness: every statement of the algorithm should be unambiguous
 Finiteness: No infinite loop should be allowed in an algorithm
 Effectiveness: The algorithm must perform each step correctly and in a finite
amount of time therefore time tends to be more important in calculating the
effectiveness of an algorithm. The space and other resources taken up by
algorithm also plays vital role in effectiveness of an algorithm.
2. List the properties of an algorithm. (Dec 20)
Simply writing the sequence of instructions as an algorithm is not sufficient to
accomplish certain task. It is necessary to have following properties associated with an
algorithm.
 Non-Ambiguity: Each step in an algorithm should be non-ambiguous. That means
each instruction should be clear and precise. The instruction in any algorithm
should not denote any conflicting meaning. This property also indicates the
effectiveness of algorithm.
 Range of Input: The range of input should be specified. This is because normally
the algorithm is input driven and if the range of input is not being specified then
algorithm can go in an infinite state.
 Multiplicity: The same algorithm can be represented into several different ways.
That means we can write in simple English the sequence of instruction or we can
write it in form of pseudo code. Similarly, for solving the same problem we can
write several different algorithms.
 Speed: The algorithm written using some specified ideas. Bus such algorithm
should be efficient and should produce the output with fast speed.
 Finiteness: The algorithm should be finite. That means after performing required
operations it should be terminate
3. Draw the notion of an algorithm

St. Joseph’s College of Engineering Page 1 of 38

CS1401- Design and Analysis of Algorithms Department of CSE, IT, ADS and AML 2023-2024
4. List the important points about algorithm.
 The nonambiguity requirement for each step of an algorithm cannot be
compromised.
 The range of inputs for which an algorithm works has to be specified carefully.
 The same algorithm can be represented in several different ways.
 There may exist several algorithms for solving the same problem.
 Algorithms for the same problem can be based on very different ideas and can
solve the problem with dramatically different speeds.
5. List the various methods for computing greatest Common Divisor of two numbers m
and n
 Consecutive integer checking algorithm for computing gcd(m, n)
 Middle-school procedure for computing gcd(m, n)
 Euclid’s algorithm for computing greatest Common Divisor gcd (m, n)
6. Give the Euclid’s algorithm for computing greatest Common Divisor gcd (m, n) in
Pseudo code format.
ALGORITHM Euclid (m, n)
//Computes gcd (m, n) by Euclid’s algorithm
//Input: Two nonnegative, not-both-zero integers m and n
//Output: Greatest common divisor of m and n
while n ≠ 0 do
r ←m mod n
m←n
n←r
return m
7. Give the Euclid’s algorithm for computing greatest Common Divisor gcd (m, n) in
structured description format.
gcd(m, n) = gcd(n, m mod n),
gcd(m, 0) = m
Euclid’s algorithm for computing gcd (m, n)
Step 1 If n = 0, return the value of m as the answer and stop; otherwise,
proceed to Step 2.
Step 2 Divide m by n and assign the value of the remainder to r.
Step 3 Assign the value of n to m and the value of r to n. Go to Step 1.
8. Write Consecutive integer checking algorithm for computing gcd (m, n) (Nov
22) Consecutive integer checking algorithm for computing gcd (m, n)
Step 1 Assign the value of min {m, n} to t.
Step 2 Divide m by t. If the remainder of this division is 0, go to Step 3;
otherwise, go to Step 4.
Step 3 Divide n by t. If the remainder of this division is 0, return the value of t
as the answer and stop; otherwise, proceed to Step 4.
Step 4 Decrease the value of t by 1. Go to Step 2.
9. Write Middle-school procedure for computing gcd (m,
n) Middle-school procedure for computing gcd (m, n)
Step 1 Find the prime factors of m.
Step 2 Find the prime factors of n.
Step 3 Identify all the common factors in the two prime expansions found in
Step 1 and Step 2. (If p is a common factor occurring pm and pn times in m and
n, respectively, it should be repeated min {pm, pn} times.)
Step 4 Compute the product of all the common factors and return it as the
greatest common divisor of the numbers given.
St. Joseph’s College of Engineering Page 2 of 38
CS1401- Design and Analysis of Algorithms Department of CSE, IT, ADS and AML 2023-2024
10. Find gcd (31415, 14142) by applying Euclid’s algorithm.
Gcd (31415, 14142) = gcd (14142, 3131)
= gcd (3131, 1618)
= gcd (1618, 1513)
= gcd (1513, 105)
= gcd (105, 43)
= gcd (43, 19)
= gcd (19, 5)
= gcd (5, 4)
= gcd (4, 1)
= gcd (1, 0)
=1
11. What are the steps involved in designing and analyzing an algorithm?
 Understanding the problem
 Decide on
 Computational Device
 Exact Vs. Approximate Algorithms
 Data Structures
 Algorithm Design Techniques
 Design an algorithms
 Prove Correctness
 Analyze the algorithm
 Code the algorithm
12. List the reasons for choosing an approximate algorithm. (Dec 20)
Approximation algorithms are efficient algorithms that find approximate
solutions to optimization problems with provable guarantees on the distance of the
returned solution to the optimal one.
The reason for opting the approximate algorithm is
 There are important problems that simply cannot be solved exactly for most
of their instances; examples include extracting square roots, solving nonlinear
equations, and evaluating definite integrals.
 Available algorithms for solving a problem exactly can be unacceptably slow
because of the problem’s intrinsic complexity. This happens, in particular, for
many problems involving a very large number of choices
 An approximation algorithm can be a part of a more sophisticated algorithm that
solves a problem exactly
13. Define algorithm design technique
An algorithm design technique (or “strategy” or “paradigm”) is a general
approach to solving problems algorithmically that is applicable to a variety of problems
from different areas of computing.
14. What are the options that are widely used for specifying algorithms?
There are the two options that are most widely used nowadays for specifying
algorithms.
 Using a natural language has an obvious appeal; however, the inherent
ambiguity of any natural language makes a succinct and clear description of
algorithms surprisingly difficult.
 Pseudo code is a mixture of a natural language and programming language like
constructs. Pseudo code is usually more precise than natural language, and its
usage often yields more succinct algorithm descriptions.

St. Joseph’s College of Engineering Page 3 of 38

CS1401- Design and Analysis of Algorithms Department of CSE, IT, ADS and AML 2023-2024
15. Mention the most important problem types
 Sorting
 Searching
 String processing
 Graph problems
 Combinatorial problems
 Geometric problems
 Numerical problems

16. List the two important properties of sorting algorithm.

 A sorting algorithm is called stable if it preserves the relative order of any two
equal elements in its input. In other words, if an input list contains two equal
elements in positions i and j where i < j, then in the sorted list they have to be
in positions i and j, respectively, such that i’< j’.
 The second notable feature of a sorting algorithm is the amount of extra memory
the algorithm requires. An algorithm is said to be in-place if it does not require
extra memory, except, possibly, for a few memory units
17. How do you measure the efficiency of an algorithm? (May 19), (May 2023)
We can measure the efficiency of an algorithm using
 Time efficiency, also called time complexity, indicates how fast an algorithm
in question runs.
 Space efficiency, also called space complexity, refers to the amount of memory
units required by the algorithm

18. What is basic operation? Give example.

The operation contributing the most to the total running time is known as basic
operation. As a rule, it is usually the most time-consuming operation in the algorithm’s
innermost loop.
For example, most sorting algorithms work by comparing elements (keys) of a
list being sorted with each other; for such algorithms, the basic operation is a key
comparison.
As another example, algorithms for mathematical problems typically involve
some or all of the four arithmetical operations: addition, subtraction, multiplication,
and division.
Of the four, the most time-consuming operation is division, followed by
multiplication and then addition and subtraction, with the last two usually considered
together
19. Write a simple formula to estimate the running time of an algorithm?
We can estimate the running time T (n) of a program implementing the
algorithm on the computer by the formula
T (n) ≈ CopC(n) where
 Cop be the execution time of an algorithm’s basic operation on a particular
computer
 C (n) be the number of times this operation needs to be executed for this algorithm.

St. Joseph’s College of Engineering Page 4 of 38

CS1401- Design and Analysis of Algorithms Department of CSE, IT, ADS and AML 2023-2024
20. Define worst-case efficiency best-case efficiency and average case efficiency
 The worst-case efficiency of an algorithm is its efficiency for the worst-case
input of size n, which is an input (or inputs) of size n for which the algorithm
runs the longest among all possible inputs of that size.
 The best-case efficiency of an algorithm is its efficiency for the best-case input
of size n, which is an input (or inputs) of size n for which the algorithm runs
the fastest among all possible inputs of that size.
 The average case efficiency of an algorithm is its efficiency for an average case
input of size n. It provides information about an algorithm behavior on a
“typical” or “random “input.

21. Define O- notation (Big oh) (Dec 21)

A function t (n) is said to be in O(g(n)), denoted t (n) ∈ O(g(n)), if t (n) is bounded
above by some constant multiple of g(n) for all large n, i.e., if there exist some positive
constant c and some nonnegative integer n0 such that
t (n) ≤ cg(n) for all n ≥ n0.

22. Define Ω-notation (Big omega) (Nov 23)

A function t (n) is said to be in Ω(g(n)), denoted t (n) ∈ Ω(g(n)), if t (n) is bounded
below by some positive constant multiple of g(n) for all large n, i.e., if there exist some
positive constant c and some nonnegative integer n0 such that
t (n) ≥ cg(n) for all n ≥ n0.

23. Define Ɵ-notation (Big theta)

A function t (n) is said to be in Ɵ (g(n)), denoted t (n) ∈ (g(n)), if t (n) is bounded
both above and below by some positive constant multiples of g(n) for all large n, i.e., if
there exist some positive constants c1 and c2 and some nonnegative integer n0 such that
c2g(n) ≤ t (n) ≤ c1g(n) for all n ≥ n0.

24. State the transpose symmetry property of O and Ω (Dec 19)

f(n) = O(g(n)) if and only if g(n) = Ω(f(n))
f(n) = o(g(n)) if and only if g(n) = ω(f(n))

St. Joseph’s College of Engineering Page 5 of 38

CS1401- Design and Analysis of Algorithms Department of CSE, IT, ADS and AML 2023-2024
25. Prove that the if f(n)= O(g(n)) and g(n)= O(f(n)), then f(n)= Θ g(n) (May 19)

Informally, f (n) = O (g (n)) means that f (n) is asymptotically less than or equal
to g (n) (1)
Informally, g (n) = O (f (n)) means that g (n) is asymptotically less than or equal
to f (n) (2) From (1) and (2) we get f(n)= Θ g(n) Informally, f(n) = Θ(g(n) means that
f(n) is
asymptotically equal to g(n)

26. Write the general plan for analyzing the time efficiency of non-recursive algorithms
(Nov 22)

 Decide on a parameter (or parameters) indicating an input’s size.

 Identify the algorithm’s basic operation. (As a rule, it is located in the innermost
loop.)
 Check whether the number of times the basic operation is executed depends only
on the size of an input. If it also depends on some additional property, the worst-
case, average-case, and, best-case efficiencies have to be investigated separately.
 Set up a sum expressing the number of times the algorithm’s basic operation
is executed
 Using standard formulas and rules of sum manipulation, either find a closed form
formula for the count or, at the very least, establish its order of growth.

27. Define Recursion. (Dec 19)
The process in which a function calls itself directly or indirectly is called recursion
and the corresponding function is called recursive function. Using recursive
algorithm, certain problems can be solved quite easily. Examples of such problems are
Towers of Hanoi (TOH), In order/Pre order/Post order Tree Traversals, DFS of Graph,
etc.

28. Write the general plan for analyzing the time efficiency of recursive algorithms

 Decide on a parameter (or parameters) indicating an input’s size.

 Identify the algorithm’s basic operation.
 Check whether the number of times the basic operation is executed can vary on
different inputs of the same size; if it can, the worst-case, average-case, and best-
case efficiencies must be investigated separately.
 Set up a recurrence relation, with an appropriate initial condition, for the
number of times the basic operation is executed.
 Solve the recurrence or, at least, ascertain the order of growth of its solution.

29. List out the properties of asymptotic notation? (Apr 22)

 Reflexivity
 Symmetry
 Transitivity
 Transpose symmetric

St. Joseph’s College of Engineering Page 6 of 38

CS1401- Design and Analysis of Algorithms Department of CSE, IT, ADS and AML 2023-2024
30. Write an algorithm (Non recursive and recursive) to find the number of binary
digits in the binary representation of a positive decimal integer.
Non recursive algorithm Recursive algorithm
ALGORITHM Binarynonrecursive(n) ALGORITHM BinRec(n)
//Input: A positive decimal integer n //Input: A positive decimal integer n
//Output: The number of binary digits in //Output: The number of binary digits in
n’s binary representation n’s binary representation
count ←1 if n = 1 return 1
while n > 1 do else return BinRec← +1
count ←count + 1
n←
return count

31. List the general plan for the empirical analysis of algorithm time efficiency (May
2023)
 Understand the experiment’s purpose.
 Decide on the efficiency metric M to be measured and the measurement unit
(an operation count vs. a time unit).
 Decide on characteristics of the input sample (its range, size, and so on).
 Prepare a program implementing the algorithm (or algorithms) for
the experimentation.
 Generate a sample of inputs.
 Run the algorithm (or algorithms) on the sample’s inputs and record the data
observed.
 Analyze the data obtained.
32. Solve the recurrence relation. (Dec 21)
T(n)=T(n-1)+5 for n>1, T(1)=0
T(n)=5(n-1)
33. What do you mean by worst case efficiency of an algorithm? (Apr 22)
The worst-case efficiency of an algorithm is its efficiency for the worst-case input of size
n, which is an input (or inputs) of size n for which the algorithm runs the longest among
all possible inputs of that size.
34. What are the steps involved in designing and analyzing an algorithm? (Nov 23)
The Steps involved in designing and analyzing an algorithm are:
1. Understand the Problem
2. Decide on: Computational Means, Exact vs Approximate solving, Algorithm design
technique.
3. Desing an algorithm
4. Prove the correctness.
5. Analyze the algorithm.
6. Code the algorithm
UNIT-I / PART-B
1 Write an algorithm using recursion that determines the GCD of two numbers.
Determine the time and space complexity. (Dec 19)
2 Explain Sieve of Eratosthenes algorithm with an example.
3 With flowchart explain the steps involved in designing and analyzing an algorithm in
detail. (May 19, Dec 21)
4 List and explain the important problem types in detail.

St. Joseph’s College of Engineering Page 7 of 38

CS1401- Design and Analysis of Algorithms Department of CSE, IT, ADS and AML 2023-2024
5 Outline the general framework for analyzing the efficiency of algorithms.
6 Write the various asymptotic notations used for best-case, worst-case and average case
analysis of algorithm. Depict the same graphically and give example. (Dec 19,20) (May
2023)
7 (i) Explain the best-case worst case and average case efficiency with sequential search
algorithm. (May 2023)
(ii) List the basic efficiency classes in increasing order of their orders of growth, along
with their names. (May 2023)
8 Discuss the general plan for analyzing the efficiency of non-recursive algorithm
9 Write a non-recursive algorithm to find the value of the largest element in a list of n
numbers and find the time complexity.
10 Design a non-recursive algorithm for computing the product of two n* n matrices and
also find the time efficiency of the algorithm. (Nov 22)
11 Write an algorithm for determining the uniqueness of an array. Determine the time
complexity of the algorithm. (Apr 22)
12 Design a non-recursive algorithm to find the number of binary digits in the binary
representation of a positive decimal integer and find the time complexity
13 Discuss the general plan for analyzing the efficiency of recursive algorithm (Nov 22)
Design a recursive algorithm to compute the factorial function F (n) =n! and derive the
recurrence relation. (Dec 20)
14 (i) Discuss algorithm for Tower of Hanoi problem. (Nov 22)
(ii) Design recursive and non-recursive algorithms for finding sum of N given numbers.
Also analyze the efficiency of these algorithms. (Apr 22)
15 Explain Empirical analysis of algorithms with example.
16 Solve the following recurrence relation

i) T(n)=T(n/2)+n for n>1 and T(1)=1 (solve for n =2k) (Apr 22)
ii) T(n)=T(n/3)+1 for n>1 and T(1)=1 (solve for n =3k) (Dec 21)
17 (i) Design an algorithm to find the greatest common divisor (GCD) using Euclid’s
algorithm, Middle school procedure and consecutive integer checking method.
(ii) Find gcd(31415, 14142) by applying Euclid’s algorithm. Estimate how many times
faster it will be to find gcd(31415, 14142) by Euclid’s algorithm compared with the
algorithm base on checking consecutive integers from min{m,n} down to gcd(m,n). (May
2023)
18 i) Design a recursive algorithm which solves the Tower of Hanoi puzzle. The objective of
the puzzle is to move ‘n’ disks form one tower to another but with some rules in place.
(ii) Write a recurrence relation to determine the number of moves in the Tower of Hanoi
puzzle. Solve the recurrence relation and find out the number of moves required for 5
disks. Show all steps. (May 2023)
19 Discuss the recurrence algorithm for Tower of Hanoi problem. Find the Recurrence
Relation and Time Complexity? (Nov 23)
20 Discuss the steps in mathematical analysis for non-recursive algorithms. Do the same for
the problem of finding the value of the largest element in a list of n numbers (Nov 23)

St. Joseph’s College of Engineering Page 8 of 38

CS1401- Design and Analysis of Algorithms Department of CSE, IT, ADS and AML 2023-2024
DECRESE AND CONQUER AND DIVIDE-AND-CONQUER
Decrease-and-Conquer– Insertion Sort – Binary Search – Computing a Median and the
Selection Problem – Divide-and-Conquer – Merge Sort – Quicksort – The Closest –Pair and
Convex –Hull Problems by Divide-and-Conquer

UNIT-II / PART-A
1 What is decrease-and-conquer technique? What are the three major variations of
decrease-and-conquer? (May 2023,Nov 23)
The decrease-and-conquer technique is based on exploiting the relationship between a
solution to a given instance of a problem and a solution to its smaller instance. Once
such a relationship is established, it can be exploited either top down or bottom up.
Three major variations of decrease-and-conquer:
 Decrease by a constant
 Decrease by a constant factor
 Variable size decrease
2 What is Decrease by a constant?
In this variation, the size of an instance is reduced by the same constant on each iteration
of the algorithm. Typically, this constant is equal to one, although other constant size
reductions do happen occasionally. Below are example problems :
 Insertion sort
 Graph search algorithms: DFS, BFS
 Topological sorting
 Algorithms for generating permutations, subsets
3 What is Decrease by a Constant factor? Give Example?
This technique suggests reducing a problem instance by the same constant factor on each
iteration of the algorithm. In most applications, this constant factor is equal to two. A
reduction by a factor other than two is especially rare. Decrease by a constant factor
algorithm is very efficient especially when the factor is greater than 2 as in the fake-coin
problem. Below are example problems :
 Binary search
 Fake-coin problems
 Russian peasant multiplication
4 What is Variable-Size-Decrease Give Example?
In this variation, the size-reduction pattern varies from one iteration of an algorithm to
another. As, in problem of finding gcd of two number though the value of the second
argument is always smaller on the right-handside than on the left-hand side, it decreases
neither by a constant nor by a constant factor. Below are example problems :
 Computing median and selection problem.
 Interpolation Search
 Euclid’s algorithm

5 What is an insertion sort?

Insertion sort is a direct application of the decrease-(by one)-and-conquer technique to
the sorting problem. It is a (n2) algorithm both in the worst and average cases, but it is
about twice as fast on average than in the worst case.
6 Write note on binary search?
Binary search is a remarkably efficient algorithm for searching in a sorted array. It
works by comparing a search key K with the array’s middle element A[m]. If they
match, the algorithm stops; otherwise, the same operation is repeated recursively
for the first half of the array if K <A[m], and for the second half if K >A[m]

St. Joseph’s College of Engineering Page 9 of 38

CS1401- Design and Analysis of Algorithms Department of CSE, IT, ADS and AML 2023-2024
7 What is the time and space complexity of binary search?
 Binary search has average and worst-case performance of O (n log n) and best
case performance as O (1).
 Space complexity of binary search is 1
8 Design a decrease-by-half algorithm for computing [log2n] and determine its time
efficiency.
Algorithm: LogFloor (n)
Input: A positive integer n
Output: Returns [log2n]
if n = 1 return 0
else return LogFloor ([n/2]) + 1
The recurrence relation for the number of additions is:
A(n) = A(|n/2|) + 1 for n > 1, A(1) = 0
Its Solution is A(n) = [log2n] ϵ 𝞠(log n)
9 Write the way to analyze the efficiency of binary search?
The standard way to analyze the efficiency of binary search is to count the number of
times the search key is compared with an element of the array. Moreover, for the sake of
simplicity, we will count the so-called three-way comparisons. This assumes that after
one comparison of K with A[m], the algorithm can determine whether K is smaller, equal
to, or larger than A[m].
10 Write the pseudocode for implementing partitioning procedure using Lomuto
Partition?
ALGORITHM LomutoPartition(A[l..r])

//Partitions subarray by Lomuto’s algorithm using first element as pivot

//Input: A subarray A[l..r] of array A[0..n − 1], defined by its left and right
// indices l and r (l ≤ r)
//Output: Partition of A[l..r] and the new position of the pivot

p←A[l]
s ←l
for i ←l + 1 to r do
if A[i]<p
s ←s + 1; swap(A[s], A[i])
swap(A[l], A[s])
return s
11 What are all the improvements that can be applied on quick sort?

 Better pivot selection methods such as randomized quicksort that uses a random
element or the median-of-three method that uses the median of the leftmost,
rightmost, and the middle element of the array
 Switching to insertion sort on very small subarrays (between 5 and 15 elements
for most computer systems) or not sorting small subarrays at all and finishing the
algorithm with insertion sort applied to the entire nearly sorted array
 Modifications of the partitioning algorithm such as the three-way partition into
segments smaller than, equal to, and larger than the pivot

St. Joseph’s College of Engineering Page 10 of 38

CS1401- Design and Analysis of Algorithms Department of CSE, IT, ADS and AML 2023-2024
12 Write the general divide and conquer approach to solve a problem. (Dec 20, 21, Apr 22)
Divide-and-conquer algorithms work according to the following general plan:
 A problem is divided into several subproblems of the same type, ideally of
about equal size.
 The subproblems are solved (typically recursively, though sometimes a
different algorithm is employed, especially when subproblems become small
enough).
 If necessary, the solutions to the subproblems are combined to get a solution
to the original problem. (Refer Figure)

13. Write the general recurrence relation for divide and conquer method?
Most typical case of divide-and-conquer a problem’s instance of size n is divided
into two instances of size n/2. More generally, an instance of size n can be divided into b
instances of size n/b, with a of them needing to be solved. (Here, a and b are constants; a
≥ 1 and b > 1.) Assuming that size n is a power of b to simplify our analysis, we get the
following recurrence for the running time T (n):
T (n) = aT (n/b) + f (n) where f (n) is a function that accounts for the time
spent on dividing an instance of size n
into instances of size n/b and combining their solutions.
14. State Master’s Theorem. (Nov 22) (May 2023)
If f (n) ∈ Ɵ (nd) where d ≥ 0 in recurrence T (n) = aT (n/b) + f (n),
then

15. Write note on mergesort

Mergesort is a divide-and-conquer sorting algorithm. It works by dividing an
input array into two halves, sorting them recursively, and then merging the two sorted
halves to get the original array sorted. The algorithm’s time efficiency is in O (n log n)
in all cases, with the number of key comparisons being very close to the theoretical
minimum. Its principal drawback is a significant extra storage requirement.
16. What is the time and space complexity of merge sort? (May 19)
 In sorting n objects, merge sort has a best, average and worst-case
performance of O (n log n).
 Space complexity of Merge Sort is O(n)

St. Joseph’s College of Engineering Page 11 of 38

CS1401- Design and Analysis of Algorithms Department of CSE, IT, ADS and AML 2023-2024
17. List the variations of merge sort or What is multiway mergesort?
 First, the algorithm can be implemented bottom up by merging pairs of the array’s
elements, then merging the sorted pairs, and so on. This avoids the time and space
overhead of using a stack to handle recursive calls.
 Second, we can divide a list to be sorted in more than two parts, sort each
recursively, and then merge them together. This scheme, which is particularly
useful for sorting files residing on secondary memory devices, is called
multiway mergesort.
18. Write note on quicksort
Quicksort is a divide-and-conquer sorting algorithm that works by partitioning
its input elements according to their value relative to some preselected element.
Quicksort is noted for its superior efficiency among n log n algorithms for sorting
randomly ordered
arrays but also for the quadratic worst-case efficiency.
19. Compare and contrast merge sort and quicksort
Mergesort and quicksort are important sorting algorithms that is based on the
divide-and conquer approach. Unlike mergesort, which divides its input elements
according to their position in the array, quicksort divides them according to their value.
In mergesort the division of the problem into two subproblems is immediate and the
entire work happens in combining their solutions whereas in quicksort, the entire work
happens in the division stage, with no work required to combine the solutions to the
subproblems.
20. What is the time and space complexity of Quick sort?
 In sorting n objects, quick sort has a best, average case performance of O (n
log n). and worst-case performance of O (n2).
 Space complexity of Merge Sort is O(log n)

21 Solve the following using Master theorem. (Nov 21, Nov 23))
A (n) = 2A (n/2) + 1.
Answer:A(n)= O(n )
22 What is convex hull problem? (Apr 22)
The convex hull of a set S of points is the smallest convex set containing S. (The “smallest”
requirement means that the convex hull of S must be a subset of any convex set containing
S.) The convex-hull problem is the problem of constructing the convex hull for a given set
S of n points.
UNIT-II / PART-B
1. Apply insertion sort to sort the list E, X, A, M, P, L, E in alphabetical order.
2. (a) Write pseudocode for a non recursive implementation of quick select.
(b) Apply the partition-based algorithm to find the median of the following list of nine
numbers: 4, 1, 10, 8, 7, 12, 9, 2, 15.
3. Explain binary search algorithm in detail. Using Binary Search, search for the elements
151, -14, and 9 in the given set of sorted elements 15, 6, 0, 7, 9, 23, 54, 82, 101, 112, 125,
131,
142, 151. Derive the time complexity also.
4. Write the algorithm for Merge sort. Apply Merge sort to sort the list 18, 13, 12, 19, 17, 11,
15, 14. Analyze the worst case and best case time complexity. (Nov 22)
5. Write pseudocode for divide-and-conquer Mergesort. Apply Merge sort to sort the list
10,8,22,45,32,21,67,39. Analyze its best-case and worst-case time complexity. (May 2023)

St. Joseph’s College of Engineering Page 12 of 38

CS1401- Design and Analysis of Algorithms Department of CSE, IT, ADS and AML 2023-2024
6. Sort the following numbers using quick sort. 999, 888, 777, 666, 555, 444, 333, 222, 111,
11,
22, 33, 44, 55, 66, 77, 88, 99. Illustrate each step in the sorting process. (Dec 19)
7. Write the algorithm to find the closest pair of points using divide and conquer and
explain it with an example. Derive the worst case and average case complexity. (Dec 19)
8. State and explain quick sort algorithm and prove that it is not a stable sorting algorithm
(Apr 22)
9. Write an algorithm using divide and conquer to search an element in a list of numbers.
If the number is not present, the algorithm returns the closest number of the
searches
number. (Dec 20)
10. Give the algorithm for Quicksort. Apply Quicksort to sort the list 5, 3, 1, 9, 8, 2, 4, 7 and
show that it is not stable sorting algorithm. Draw the tree for the recursive calls made.
Analyze the time complexity. (Nov 21)
11. Write pseudo code for implementing Lomuto Partitioning. Apply the partition-based
algorithm to find the median of the following list of nine numbers: 4,1,10,8,7,12,9,2 and
15. (May 2023)

12. Trace the operation of binary search algorithm for the input -15,-
6,0,7,9,23,54,82,101,112,125,131,142,151 if you are searching for element 9. Explain the
algorithm and analyze the time complexity of binary search in worst case and best case.
(Nov 23)
13. Explain the various steps involved in decrease-by-constant method and sort the following
5,9,8,7,6 using insertion sort. Analyze its time complexity (Nov 23)
DYNAMIC PROGRAMMING AND GREEDY TECHNIQUE
The Knapsack Problem and Memory Functions – Optimal Binary Search Trees – Warshall’s
Algorithm – Floyd’s Algorithm – Greedy Technique – Prim’s Algorithm – Kruskal’s Algorithm
– Dijkstra’s Algorithm – Huffman Trees and Code
UNIT-III/ PART-A
1. What is dynamic programming?
Dynamic programming is a technique for solving problems with overlapping
subproblems. Typically, these subproblems arise from a recurrence relating a given
problem’s solution to solutions of its smaller subproblems. Rather than solving
overlapping subproblems again and again, dynamic programming suggests solving
each of the smaller subproblems only once and recording the results in a table from
which a solution to the original problem can then be obtained.
2. What does dynamic programming have in common with divide-and-conquer?
Both techniques are based on dividing a problem’s instance into smaller instances of the
same problem.
3. What is a principal difference and similarity between dynamic programming and
divide-and conquer? (Nov 22) (May 2023)
Typically, divide-and-conquer divides an instance into smaller instances with no
intersection whereas dynamic programming deals with problems in which smaller
instances overlap. Consequently, divide-and-conquer algorithms do not explicitly store
solutions to smaller instances and dynamic programming algorithms do. Dynamic
programming is similar to the divide and conquer strategy since it breaks down the
problem into smaller sub-problems.

St. Joseph’s College of Engineering Page 13 of 38

CS1401- Design and Analysis of Algorithms Department of CSE, IT, ADS and AML 2023-2024
4. What is meant by optimal substructure property of a dynamic programming problem?
(Dec 20)
Optimal substructure property states that the optimal solution of the given
problem can be obtained by finding the optimal solutions of all the sub-problems. In
other words, we can solve larger problems given the solution of smaller problems.
Suppose we have given a complex problem, then we will break this problem into
simpler problems optimally to find the optimal solution of the given complex problem

5. State coin change problem.

Given an unlimited supply of coins of given denominations, find the total
number of distinct ways to get the desired change. For example S ={1,3,5,7} and
target = 8. The total number of ways is =6. They are {1,7} {3,5} {1,1,3,3} {1,1,1,5}
{1,1,1,1,1,3} {1,1,1,1,1,1,1,1}
6. Write the equation for calculating binomial coefficient. (Dec 21)
The value of C (n, k) can recursively calculated using following standard formula for
Binomial coefficients that k objects can be chosen from among n objects.
C(n, k) = C(n-1, k-1) + C(n-1, k)
C(n, 0) = C(n, n) = 1
7. Define adjacency matrix and transitive closure
The adjacency matrix A = {aij} of a directed graph is the boolean matrix that has 1 in its
ith row and jth column if and only if there is a directed edge from the ith vertex to the
jth vertex. The transitive closure of a directed graph with n vertices can be defined as
the n × n boolean matrix T = {tij}, in which the element in the ith row and the jth column
is 1 if there exists a nontrivial path (i.e., directed path of a positive length) from the ith
vertex to the jth vertex; otherwise, tij is 0.

8. What is all-pairs shortest paths problem?

Given a weighted connected graph (undirected or directed), the all-pairs
shortest paths problem asks to find the distances—i.e., the lengths of the shortest
paths— from each vertex to all other vertices.
9. What is Binary Search Tree? (Dec 19)
A binary search tree is a binary tree with the following properties:
 The left sub-tree of a node N contains values that are less than N’s value.
 The right sub-tree of a node N contains values that are greater than N’s value.
 Both the left and the right binary trees also satisfy these properties and, thus,
are binary search trees.

10. What is memory function technique?

The memory function technique seeks to combine the strengths of the topdown and
bottom-up approaches to solving problems with overlapping subproblems. It does this
by solving, in the top-down fashion but only once, just the necessary subproblems of
a given problem and recording their solutions in a table.

St. Joseph’s College of Engineering Page 14 of 38

CS1401- Design and Analysis of Algorithms Department of CSE, IT, ADS and AML 2023-2024
11. What is greedy technique?
The greedy technique suggests constructing a solution to an optimization problem
through a sequence of steps, each expanding a partially constructed solution obtained
so far, until a complete solution to the problem is reached. On each step, the choice
made must be feasible, locally optimal, and irrevocable.
12. Write Floyd’s algorithm for the all-pairs shortest-paths problem
ALGORITHM Floyd(W[1..n, 1..n])
//Implements Floyd’s algorithm for the all-pairs shortest-paths problem
//Input: The weight matrix W of a graph with no negative-length cycle
//Output: The distance matrix of the shortest paths’ lengths
D ←W //is not necessary if W can be overwritten
for k←1 to n do
for i ←1 to n do
for j ←1 to n do
D[i, j ]←min{D[i, j ], D[i, k]+ D[k, j]}
return D
13. What is the constraint for binary search tree insertion? (May 19)
Inserting a node in a given Binary Search Tree is a process to add a new node; let’s
say if node A has to be inserted then you got to follow below steps –
 STEP 1: If there is no node in a given BST then insert node A as its Root
Node.
 STEP 2: Find the Node in a given Binary Search Tree where we need to
insert A (as either left or a right child). To find so, just compare the value
of node A with the root node’s value:
if node A has a value greater than the root node’s value – traverse down the root
node in its right node and Go to Step 2 by considering this right node as the root
node (Note: if there is no right node straight go to Step 3) if node A has a value
lesser than the root node’s value – traverse down the root node in its left node
and Go to Step 2 by considering this left node as the root node (Note: if there is
no left node straight go to Step 3)
 STEP 3: Once the Node is found using step 1:
if value of node A is greater than this Node’s value – insert A as the right child of
this node. If value of node A is lesser than this Node’s value – insert A as the left
child of this node
14. Define feasible, locally optimal and irrevocable
 Feasible : It has to satisfy the problem’s constraints
 locally optimal: It has to be the best local choice among all feasible choices
available on that step
 irrevocable: Once made, it cannot be changed on subsequent steps of the
algorithm
15. Outline Prim’s algorithm that constructs a minimum spanning tree
Prim’s algorithm constructs a minimum spanning tree through a sequence of expanding
subtrees. The initial subtree in such a sequence consists of a single vertex selected
arbitrarily from the set V of the graph’s vertices. On each iteration, the algorithm
expands the current tree in the greedy manner by simply attaching to it the nearest
vertex not in that tree. The algorithm stops after all the graph’s vertices have been
included in the tree
being constructed.

St. Joseph’s College of Engineering Page 15 of 38

CS1401- Design and Analysis of Algorithms Department of CSE, IT, ADS and AML 2023-2024
16. Write the control abstraction for greedy method (Dec 2020)
Algorithm Greedy (a, n)
// a [1: n] contains n inputs
{
Solution: =
0; for i: =1 to
n do
{
x := select(a);
if feasible(solution, x) then
Solution: = Union (solution,
x);
}
return solution; }
17. Define spanning tree, minimum spanning tree
 A spanning tree of an undirected connected graph is its connected acyclic
subgraph (i.e., a tree) that contains all the vertices of the graph.
 If such a graph has weights assigned to its edges, a minimum spanning tree is
its spanning tree of the smallest weight, where the weight of a tree is defined as
the sum of the weights on all its edges.
 The minimum spanning tree problem is the problem of finding a minimum
spanning tree for a given weighted connected graph.

18. List the drawbacks of constructing a minimum spanning tree by exhaustive search
If we were to try constructing a minimum spanning tree by exhaustive search,
we would face two serious obstacles.
 First, the number of spanning trees grows exponentially with the graph size (at
least for dense graphs).
 Second, generating all spanning trees for a given graph is not easy; in fact, it is
more difficult than finding a minimum spanning tree for a weighted graph
by using one of several efficient algorithms available for this problem.
19. How efficient is Prim’s algorithm?
 If a graph is represented by its weight matrix and the priority queue is
implemented as an unordered array, the algorithm’s running time will be in
Ɵ (|V |2).
 If a graph is represented by its adjacency lists and the priority queue is
implemented as a min-heap, the running time of the algorithm is
in O (|E| log |V |).

20. Outline Kruskal’s algorithm that constructs a minimum spanning tree

Kruskal’s algorithm is greedy algorithm for the minimum spanning tree problem.
It constructs a minimum spanning tree by selecting edges in nondecreasing order of
their weights provided that the inclusion does not create a cycle. Checking the latter
condition
efficiently requires an application of union-find algorithms.

St. Joseph’s College of Engineering Page 16 of 38

CS1401- Design and Analysis of Algorithms Department of CSE, IT, ADS and AML 2023-2024
21. State 0/1 Knapsack problem. (Nov 23)
Given weights and values of n items, put these items in a knapsack of capacity W
to get the maximum total value in the knapsack. In other words, given two integer
arrays val[0..n-1] and wt[0..n-1] which represent values and weights associated with n
items respectively. Also given an integer W which represents knapsack capacity, find
out the maximum value subset of val[] such that sum of the weights of this subset is
smaller than or equal to W. You cannot break an item, either pick the complete item
or don’t pick it (0-1 property).
22. Differentiate fixed-length encoding and Variable-length encoding
 Fixed-length encoding that assigns to each symbol a bit string of the same
length Variable-length encoding, which assigns code words of different lengths to
different symbols

23. Define Huffman tree

A Huffman tree is a binary tree that minimizes the weighted path length from the root to
the leaves of predefined weights. The most important application of Huffman trees is
Huffman codes.

24. Give the difference between Dynamic Programming and Greedy technique. (Apr 22)
Dynamic programming is a technique for The greedy technique suggests
solving problems with overlapping constructing a solution to an optimization
subproblems. Typically, these subproblems problem through a sequence of steps, each
arise from a recurrence relating a given expanding a partially constructed solution
problem’s solution to solutions of its smaller obtained so far, until a complete solution
subproblems. Rather than solving to the problem is reached. On each step,
overlapping subproblems again and again, the choice made must be feasible, locally
dynamic programming suggests solving optimal, and irrevocable.
each of the smaller subproblems only once
and recording the results in a table from
which a solution to the original problem can
then be obtained.
We choose at each step, but the choice may We make whatever choice seems best at
depend on the solution to sub-problems. the moment and then solve the sub-
problems arising after the choice is made.
It is guaranteed to generate an optimal No such guarantee of getting Optimal
solution using Principle of Optimality. Solution.
25. Find the solution for Coin changing using dynamic programming for $5 with
denominations 1, 2, 3. (Apr 22)
NUMBER OF WAYS
The Number of Ways = 5
(OR)
MINIMUM NUMBER OF COINS
The Minimum Number of Coins = 2
26. Define Huffman code
A Huffman code is an optimal prefix-free variable-length encoding scheme that assigns
bit strings to symbols based on their frequencies in a given text. This is accomplished by
a greedy construction of a binary tree whose leaves represent the alphabet symbols and
whose edges are labeled with 0’s and 1’s.

St. Joseph’s College of Engineering Page 17 of 38

CS1401- Design and Analysis of Algorithms Department of CSE, IT, ADS and AML 2023-2024
27. What is Catalan number? (Nov 21,Nov 23)
Catalan numbers is a number sequence, which is found useful in a number of
combinatorial problems, often involving recursively-defined objects. They satisfy a
fundamental recurrence relation, and have a closed-form formula in terms of binomial
coefficients.

UNIT-III / PART-B
1. Explain how dynamic programming technique is applied to compute binomial
coefficient
for C (6, 3) and analyze the time complexity with algorithm. (Dec 21)
2. Solve the all-pairs shortest path problem for the digraph with the following weight
matrix (Apr 22)

Prove that the time efficiency of Floyd’s algorithm is cubic

3. Write the Floyd algorithm to find all pairs shortest path and derive its time complexity.
(May 19)
4. Solve the following using Floyd’s algorithm. (May 19)

5. Compare and contrast dynamic programming and greedy method. (Dec 20)
6. Outline the dynamic programming approach to solve the optimal binary tree search
problem and analyze its time complexity. (Dec 19)
7. Explain an algorithm to find optimal binary search tree with example. (Dec 21)
Key A B C D
Probability 0.1 0.2 0.4 0.3

Also prove that this could be performed in time O(n3)

8. Construct the optimal binary search tree for the following 5 keys with probabilities as
indicated. (Dec 19)
i 0 1 2 3 4 5
pi 0.15 0.10 0.05 0.10 0.20
qi 0.05 0.10 0.05 0.05 0.05 0.10

St. Joseph’s College of Engineering Page 18 of 38

CS1401- Design and Analysis of Algorithms Department of CSE, IT, ADS and AML 2023-2024
9. Write memory function algorithm to solve the following knapsack problem. (Nov 22)

Knapsack Capacity W=5

10. Apply the dynamic programming algorithm (bottom up) to solve the following
instance of the knapsack problem and explain in detail.

Knapsack capacity W=6

11. Write the algorithm for optimal binary search tree and solve the following problem
instance to construct the optimal binary search tree. Keys are a, b, c, d and the
probabilities are 0.1, 0.2, 0.4 and 0.3. (Dec 20)
12. Write greedy algorithm to solve the 0/1 knapsack problem. Analyze its time complexity.
Show that this algorithm is not optimal with an example. (Dec 19)
13. Apply memory function for the following knapsack problem of capacity W=5 (Apr 22)

14. Write the prim’s algorithm to find the minimum spanning tree and illustrate the
algorithm for the following graph. Where a, b, c, d and e are nodes and each edges
are weighted by numbers. (Dec 20)

15. Write the Huffman code algorithm and derive its time complexity. (May 19)
16. Generate the Huffman code for the following data comprising alphabet and their
frequency: a: 1, b: 1, c: 2, d: 3, e: 5, f: 8, g: 13, h: 21. (May 19)
17. Let A = {l/119, m/96, c/247, g/283, h/72, f/77, k/92, j/19} be the letters and its frequency
of distribution in a text file. Compute a suitable Huffman coding to compress the data
effectively.
18. Find Optimal BST (Apr 22)

St. Joseph’s College of Engineering Page 19 of 38

CS1401- Design and Analysis of Algorithms Department of CSE, IT, ADS and AML 2023-2024
19. (i) Construct a Huffman code for the following data:

(ii) Encode ABACABAD using the code of question (i)

(iii) Decode 100010111001010 using the code of question (i)
20. Find minimum spanning tree of the following graph using Prim’s algorithm and
Kruskal’s algorithm (Nov 22)

21. Write Warshall’s algorithm for computing transitive closure. Apply Warshall’s algorithm
to find the transitive closure of the digraph defined by the following adjacency matrix.
(May 2023)

Also prove that the time efficiency of Warshall’s Algorithm is cubic

22. A file contains the following characters with the probabilities as shown in the table. IF
Huffman coding is used for data compression, determine
Characters a e i o u s t
Probabiliti 0.17 0.26 0.2 0.05 0.07 0.22 0.0
es 1 2
(i) Huffman Code for each character
(ii) Average number of bits per symbol
(iii) Compression Ratio (May 2023)
23. Write the pseudo code for prim’s algorithm and apply the same to find the minimum
spanning tree for the following graph. Analyze the time complexity. (Nov 2023)

St. Joseph’s College of Engineering Page 20 of 38

CS1401- Design and Analysis of Algorithms Department of CSE, IT, ADS and AML 2023-2024
24 Write Floyd’s algorithm for the all pairs shortest path problem. Find the length of the
shortest path between all pairs of vertices of the following graph. (Nov 23)

25. Write pseudo code for Kruskal’s algorithm and apply the same to find the minimum
spanning tree for the following graph.Analyze its time complexity.(Nov 23)

ITERATIVE IMPROVEMENT
The Simplex Method - The Maximum-Flow Problem – Maximum Matching in Bipartite
Graphs, Stable marriage Problem.
UNIT-IV / PART-A
1. What is meant by Iterative improvement technique? (Dec 20)
Iterative improvement technique starts with some feasible solution (a solution
that satisfies all the constraints of the problem) and proceeds to improve it by repeated
applications of some simple step. This step typically involves a small, localized change
yielding a feasible solution with an improved value of the objective function. When no
such change improves the value of the objective function, the algorithm returns the last
feasible solution as optimal and stops.

2. List out some important problems that can be solved by iterative improvement
algorithms (Nov 22)
 Linear programming (the simplex method, the classic algorithm for linear
programming)
 Maximum flow problem
 Maximum matching in bipartite graph
 Stable marriage problem

3. State the general form of linear programming Problem. (Dec 21) (May 2023)
Linear programming Problem- the general problem of optimizing a linear
function of several variables subject to a set of linear constraints:

St. Joseph’s College of Engineering Page 21 of 38

CS1401- Design and Analysis of Algorithms Department of CSE, IT, ADS and AML 2023-2024
4. List the various obstacles to the successful implementation of iterative improvement
technique.
There can be several obstacles to the successful implementation of this idea.
 First, we need an initial feasible solution. For some problems, we can always start
with a trivial solution or use an approximate solution obtained by some other
(e.g., greedy) algorithm. But for others, finding an initial solution may require as
much effort as solving the problem after a feasible solution has been identified.
 Second, it is not always clear what changes should be allowed in a feasible solution
so that we can check efficiently whether the current solution is locally optimal and,
if not, replace it with a better one.
 Third—and this is the most fundamental difficulty— is an issue of local versus
global extremum (maximum or minimum).

5. State Extreme Point Theorem

Any linear programming problem with a nonempty bounded feasible region
has an optimal solution; moreover, an optimal solution can always be found at an
extreme
point of the problem’s feasible region
6. List the requirements of the standard form of LPP.
The standard form has the following requirements:
 It must be a maximization problem.
 All the constraints (except the nonnegativity constraints) must be in the form of
linear equations with nonnegative right-hand sides.
 All the variables must be required to be nonnegative.
7. Define feasible solution, feasible region and optimal solution?
 A feasible solution is any point) that satisfies all the constraints of the problem
 Feasible region is the set of all its feasible points.
 Optimal solution, a point in the feasible region with the largest value of
the objective function
8. Write the standard form of LPP mathematically?
The general linear programming problem in standard form with m constraints
and
n unknowns (n ≥ m) is

St. Joseph’s College of Engineering Page 22 of 38

CS1401- Design and Analysis of Algorithms Department of CSE, IT, ADS and AML 2023-2024
9. When a linear program is said to be unbounded? (Dec 2019)
A solution which increases or decreases the value of objective function of the
LP problem indefinitely is called unbounded solution.
Minimize z = 40x1 + 60x2 subject to 2x1 + x2 ≥ 70, x1 + x2 ≥ 40, x1
+ 3x2 ≥ 90 x1, x2 ≥ 0

The corner points of feasible region are P, Q, and R. The values of objective
function at corner points are 4200, 2280 and 3600. But there exists infinite number of
points in the feasible region which is unbounded. The value of objective function will
be more than the value of these three corner points i.e. the maximum value of the
objective
function occurs at a point at ∞. Hence the given problem has unbounded solution.
10. When a linear program is said to be infeasible?
The set of values of decision variables Xj (j=1 2……n) which do not satisfy all the
constraints and non-negativity conditions of an LP problem simultaneously is said to
constitute the infeasible solution to that linear programming problem
Minimize z = 200x1 + 300x2
subject to
2x1 + 3x2 ≥ 1200
x1 + x2 ≤ 400
2x1 + 1.5x2 ≥ 900
x1, x2 ≥ 0

The region located on the right of PQR includes all solutions, which satisfy the
first and the third constraints. The region located on the left of ST includes all solutions,
which satisfy the second constraint. Thus, the problem is infeasible because there is no
set of points that satisfy all the three constraints.

St. Joseph’s College of Engineering Page 23 of 38

CS1401- Design and Analysis of Algorithms Department of CSE, IT, ADS and AML 2023-2024
11. Define slack variable? (Apr 22)
If a constraint is given as an inequality, it can be replaced by an equivalent
equation by adding a slack variable representing the difference between the two sides
of the original inequality. For example, the two inequalities of problem can be
transformed, respectively into the following equations:
Maximize 3x + 5y
Subject to x+y≤4
x + 3y ≤ 6
x ≥ 0, y ≥ 0.
x + y + u = 4 where u ≥ 0 and x + 3y +v = 6 where v ≥ 0
12. Define basic solutions, basic variable, non-basic variable and basic feasible solution
 For a set of m simultaneous equations in n variables, a solution obtained by setting
(n-m) variables equal to zero and solving for remaining m equations in m variables
is called a basic solution.
 The (n-m) variables whose values did not appear in this solution are called non
basic variable and the remaining m variables are called basic variables.
 A feasible solution to an LP problem which is also the basic solution is called the
basic feasible solution. All basic variables assume non-negative values.
13. State the principle of duality. (May 19)
The Duality in Linear Programming states that every linear programming
problem has another linear programming problem related to it and thus can be derived
from it. The original linear programming problem is called “Primal,” while the derived
linear
problem is called “Dual.”
14. What are the essential properties of a flow graph? (Dec 20,Nov 23)
The transportation network can be represented by a connected weighted digraph
with n vertices numbered from 1 to n and a set of edges E, with the following properties:
 It contains exactly one vertex with no entering edges; this vertex is called the
source and assumed to be numbered 1.
 It contains exactly one vertex with no leaving edges; this vertex is called the sink
and assumed to be numbered n.
 The weight uij of each directed edge (i, j ) is a positive integer, called the edge
capacity. (This number represents the upper bound on the amount of the material
that can be sent from i to j through a link represented by this edge.)
A digraph satisfying these properties is called a flow network or simply a network. A
small instance of a network is given in Figure.

St. Joseph’s College of Engineering Page 24 of 38

CS1401- Design and Analysis of Algorithms Department of CSE, IT, ADS and AML 2023-2024
15. What is flow-conservation requirement?
The total amount of the material entering an intermediate vertex must be equal
to the total amount of the material leaving the vertex. This condition is called the flow-
conservation requirement. If we denote the amount sent through edge (i, j ) by xij , then
for any intermediate vertex i, the flow-conservation requirement can be expressed by
the following equality constraint:

where the sums in the left- and right-hand sides express the total inflow and outflow
entering and leaving vertex i, respectively.
16. What do you mean by value of the flow?
The total amount of the material leaving the source must end up at the sink.
Thus, we have the following equality

This quantity, the total outflow from the source—or, equivalently, the total inflow into
the sink—is called the value of the flow. We denote it by v. It is this quantity that we will
want to maximize over all possible flows in a network.
17. What do you mean by flow in network?
A (feasible) flow is an assignment of real numbers xij to edges (i, j ) of a given
network that satisfy
 Flow-conservation constraints and the
 Capacity Constraints 0 ≤ xij ≤ uij for every edge (i, j) ϵ E.
18. Define the capacity constraint in the context of maximum flow problem. (May 19)
0 ≤ xij ≤ uij for every edge (i, j) ϵ E where
 uij represents the weight of each directed edge (i, j) is a positive integer, called
the edge capacity
 xij represents the amount sent through edge (i, j )
19. State the maximum-flow problem formally.
The maximum-flow problem can be stated formally as the following
optimization problem:

20. Outline Ford-Fulkerson method (augmenting-path method)

Start with the zero flow (i.e., set xij = 0 for every edge (i, j ) in the network). Then,
on each iteration, try to find a path from source to sink along which some additional
flow can be sent. Such a path is called flow augmenting. If a flow-augmenting path is
found, we adjust the flow along the edges of this path to get a flow of an increased value
and try to find an augmenting path for the new flow. If no flow-augmenting path can
be found, we conclude that the current flow is optimal. This general template for solving
the maximum-flow problem is called the augmenting-path method, also known as the
Ford-Fulkerson method

St. Joseph’s College of Engineering Page 25 of 38

CS1401- Design and Analysis of Algorithms Department of CSE, IT, ADS and AML 2023-2024
21. Define cut.
An s-t cut is a set of edges whose removal disconnects t from s. Or, formally, a cut is a
partition of the vertex set into two pieces A and B where s ∈ A and t ∈ B. (The edges
of the cut are then all edges going from A to B).
22. Define capacity of a cut
The capacity of a cut (A, B) is the sum of capacities of edges in the cut. Or, in the formal
viewpoint, it is the sum of capacities of all edges going from A to B. (Don’t include the
edges from B to A.)
23. State Max-Flow Min-Cut Theorem (Nov 21)
The value of a maximum flow in a network is equal to the capacity of its minimum cut.
24. What is residual network in the context of flow networks (Dec 19)
Given a flow f in graph G, the residual graph Gf is the directed graph with all
edges of positive residual capacity, each one labeled by its residual capacity. Note: this
may include back-edges of the original graph G. (Residual Graph of a flow network is
a graph which indicates additional possible flow. If there is a path from source to sink
in residual graph, then it is possible to add flow. Every edge of a residual graph has a
value called residual capacity which is equal to original capacity of the edge minus
current flow. Residual capacity is basically the current capacity of the edge)
25. Define matching, maximum cardinality matching and maximum-matching problem
 A matching in a graph is a subset of its edges with the property that no two
edges share a vertex.
 A maximum matching or a maximum cardinality matching is a matching with
the largest number of edges.
 The maximum-matching problem is the problem of finding a maximum matching
in a given graph.
26. What is bipartite graph? (Nov 22) (May 2023)
Bipartite graph is a graph where all the vertices can be partitioned into two
disjoint sets V and U, not necessarily of the same size, so that every edge connects a
vertex in one of these sets to a vertex in the other set. In other words, a graph is bipartite
if its vertices can be colored in two colors so that every edge has its vertices colored in
different colors; such graphs are also said to be 2-colorable. The graph in Figure is
bipartite graph

27. Define augmentation

Since the length of an augmenting path is always odd, adding to the matching M the
path’s edges in the odd-numbered positions and deleting from it the path’s edges in the
even-numbered positions yields a matching with one more edge than in M. Such a
matching adjustment is called augmentation.

St. Joseph’s College of Engineering Page 26 of 38

CS1401- Design and Analysis of Algorithms Department of CSE, IT, ADS and AML 2023-2024
28. What is matched and unmatched vertices in maximum matching problem? Give
example.
 Matched (has a mate) vertices: serves as an endpoint of an edge in M,
 Unmatched (also called free) vertices:vertices that are not incident to any edge
in M
For example, for the matching Ma = {(4, 8), (5, 9)} in the graph in Figure, vertices
1, 2, 3, 6, 7, and 10 are free, and vertices 4, 5, 8, and 9 are matched.

29. Define augmenting with respect to the matching M. Give example

A simple path from a free vertex in V to a free vertex in U whose edges are
alternately in E −M and in M. That is, the first edge of the path does not belong to M, the
second one does, and so on, until the last edge that does not belong to M. Such a path is
called augmenting with respect to the matching M. For example, the path 2, 6, 1, 7 is an
augmenting path with respect to the matching Mb in Figure

30. What do you mean by perfect matching in bipartite graph?

Perfect matching is a matching (A matching in a graph is a subset of its edges
with the property that no two edges share a vertex) that matches all the vertices of the
graph.

31. How efficient is the maximum-matching algorithm?

Each iteration except the last one matches two previously free vertices—one from
each of the sets V and U. Therefore, the total number of iterations cannot exceed ⌊n/2⌋ +
1, where n = |V | + |U| is the number of vertices in the graph. The time spent on each
iteration is in O (n + m), where m = |E| is the number of edges in the graph. Hence, the
time efficiency of the algorithm is in O (n (n + m)).

St. Joseph’s College of Engineering Page 27 of 38

CS1401- Design and Analysis of Algorithms Department of CSE, IT, ADS and AML 2023-2024
32. What is maximum-weight matching?
Some applications may require taking into account the quality or cost of matching
different pairs. For example, workers may execute jobs with different efficiencies, or
girls may have different preferences for their potential dance partners. It is natural to
model such situations by bipartite graphs with weights assigned to their edges. This
leads to the problem of maximizing the sum of the weights on edges connecting matched
pairs of
vertices. This problem is called maximum-weight matching.
33. State stable marriage problem
Consider a set Y = {m1, m2, . . . , mn } of n men and a set X = {w1, w2, . . . , wn} of
n women. Each man has a preference list ordering the women as potential marriage
partners with no ties allowed. Similarly, each woman has a preference list of the men,
also with no ties. Examples of these two sets of lists are given in Figures

34. What is marriage matching problem?

A marriage matching M is a set of n (m, w) pairs whose members are selected from
disjoint n-element sets Y and X in a one-one fashion, i.e., each man m from Y is
paired with exactly one woman w from X and vice versa.

35. When a marriage matching is said to be stable?

A marriage matching M is called stable if there is no blocking pair for it; otherwise, M is
called unstable. According to this definition, the marriage matching in Figure is
unstable because Bob and Lea can drop their designated mates to join in a union they
both prefer.
36. What is ranking matrix in stable marriage problem?
The preference list can be presented by an n × n ranking matrix).The rows and
columns of the matrix represent the men and women of the two sets, respectively. A cell
in row m and column w contains two rankings: the first is the position (ranking) of w in
the m’s preference list; the second is the position (ranking) of m in the w’s preference list.
For example, the pair 3, 1 in Jim’s row and Ann’s column in the matrix in Figure indicates
that Ann is Jim’s third choice while Jim is Ann’s first.

37. Define blocking pair in stable marriage problem.

A pair (m, w), where m ∈ Y, w ∈ X, is said to be a blocking pair for a marriage
matching M if man m and woman w are not matched in M but they prefer each other to
their mates in M. For example, (Bob, Lea) is a blocking pair for the marriage matching
M= {(Bob, Ann), (Jim, Lea), (Tom, Sue)} (Refer previous Figure) because they are
not matched in M while Bob prefers Lea to Ann and Lea prefers Bob to Jim.

St. Joseph’s College of Engineering Page 28 of 38

CS1401- Design and Analysis of Algorithms Department of CSE, IT, ADS and AML 2023-2024
38. Define stable marriage problem.
The stable marriage problem is to find a stable marriage matching for men’s and
women’s given preferences.
39. Prove that the stable marriage algorithm terminates after no more than n2 iterations
with a stable marriage output. (Nov 23)
The algorithm starts with n men having the total of n2 women on their ranking lists. On
each iteration, one man makes a proposal to a woman. This reduces the total number of
women to whom the men can still propose in the future because no man proposes to the
same woman more than once. Hence, the algorithm must stop after no more than n2
iterations
40. Stable marriage problem is not “gender neutral.” Justify.
The stable marriage algorithm has a notable shortcoming. It is not “gender
neutral.” In the form presented above, it favors men’s preferences over women’s
preferences. We can easily see this by tracing the algorithm on the following instance of
the problem:
Woman1 Woman 2
Man 1 1,2 2,1
Man 2 2,1 1,2
The algorithm obviously yields the stable matching M = {(man 1, woman 1), (man 2,
woman 2)}. In this matching, both men are matched to their first choices, which is not the
case for the women. One can prove that the algorithm always yields a stable matching
that is man-optimal: it assigns to each man the highest-ranked woman possible under
any stable marriage. Of course, this gender bias can be reversed, but not eliminated, by
reversing the roles played by men and women in the algorithm, i.e., by making women
propose and men accept or reject their proposals.
41. Define maximum matching in a Bipartite Graph. (Apr 22)
A matching in a Bipartite Graph is a subset of its edges with the property that no two
edges share a vertex. A maximum matching or a maximum cardinality matching is a
matching with the largest number of edges. The maximum-matching problem is the
problem of finding a maximum matching in a given Bipartite Graph
UNIT-IV / PART-B
1. What is iterative improvement? Elaborate the steps in the simplex method with an
example. (Dec 19)
2. Elaborate the geometrical representation of linear programing with example.

3. (a) Write the summary of simplex algorithm. (7) (Nov 22)

(b) Explain the following variations of graphical method with example (6)
i) Alternate optimal solution
ii) Unbounded solution
iii) Infeasible solution
4. Solve the following using simplex method:
Maximize p = 2x + 3y + z
subject to
x + y + z ≤ 40
2x + y - z ≥
10
-y +z ≥ 10
x ≥ 0, y ≥ 0 , z ≥ 0
St. Joseph’s College of Engineering Page 29 of 38
CS1401- Design and Analysis of Algorithms Department of CSE, IT, ADS and AML 2023-2024
5. i) Solve the following linear programming
problem geometrically. Max 3x + y
Subject to -x + y ≤
1 2x+ y ≤ 4
x≥0,y≥0
ii) Solve the following linear programming
problem geometrically. Max 3x + 5y
Subject to x + y ≥4
X+ 3y ≥6
x≥0,y≥0
6. Solve the following set of equations using simplex algorithm: (May 19)
Maximize 18x1
+ 2.5x2
Subject to x1 ≤ 12
x2 ≤ 16
x ≥ 0, y ≥ 0.
x1 ≥ 0 and x2 ≥ 0
7. Determine the max-flow in the following network. (May 19)
S to 1: 4, S to 4: 2, 1 to 3: 2, 4 to 3: 1, 3 to 2: 1, 3 to t: 1, 2 to t: 3, 4 to t: 3
8. Solve the following using simplex method Maximize Z=5X1+7X2 subject to X1+X2≤4,
3X1+8X2≤24, 10X1+7X2≤35 , X1& X2≥0 (Apr 22)
9. How do you compute maximum flow for the following graph using Ford-
Fulkerson graph? Also find the minimum cut. (Nov 22)

10. State and prove max flow min cut theorem

11. Write down the optimality condition and algorithmic implementation for
finding M-augmenting paths in bipartite graph.
12. Explain the maximum-bipartite-matching problem with an illustration. (Dec 20)
13. What is bipartite graph? Is the subset of a bipartite graph bipartite? Outline with an
example. (Dec 19)
14. Apply the maximum-matching algorithm to the following bipartite graph:

Analyze the time complexity of maximum-matching algorithm.

15. Outline the stable marriage problem with an example. (Dec 19)

St. Joseph’s College of Engineering Page 30 of 38

CS1401- Design and Analysis of Algorithms Department of CSE, IT, ADS and AML 2023-2024
16. Write stable marriage algorithm. Find a stable marriage matching for the instance
defined by the following ranking matrix:
Ann Lea Sue
Bob 2,3 1,2 3,3
Jim 3,1 1,3 2,1
Tom 3,2 2,1 1,2
Analyze the time complexity of stable marriage algorithm (Nov 21)
17. Find a stable marriage matching for the instance defined by the following ranking
matrix: Determine the time efficiency of the above algorithm in the worst case.
(Dec 20,Nov 21,Nov 23)

A B C D
α 1,3 2,3 3,2 4,3
β 1,4 4,1 3,4 2,2
ϒ 2,2 1,4 3,3 4,1
δ 4,1 2,2 3,1 1,4

18. (i) Write the summary of simplex method.

(ii) Solve the following LPP by simplex
method. Max 3x + 5y
Subject to x+y≤4
x + 3y ≤ 6 x ≥ 0,y ≥ 0(Nov 21)
19. Find Max-flow and Min-cut value for the maximum flow problem given below:
(Apr 22)

20. Consider the following flow network with source ‘s’ and sink ‘t’ where edges are
labelled with their capacities:

(i) Find the maximum s-t flow for this network. What is the value of this flow?
(ii) Draw the residual network corresponding to the maximum flow found in
part (i)
(iii) Find a minimum s-t cut for this network. What is the capacity of this
cut? (May 2023)

St. Joseph’s College of Engineering Page 31 of 38

CS1401- Design and Analysis of Algorithms Department of CSE, IT, ADS and AML 2023-2024
21 Consider an instance of the stable-marriage problem given by the following
ranking matrix

W1 W2 W3
M1 1,3 2,2 3,1
M2 3,1 1,3 2,2
M3 2,2 3,1 1,3

(i) Find a stable marriage matching for this instance by applying the stable
marriage algorithm.
(ii) Find two marriage matchings that are unstable, For each exhibit a blocking
pair. (May 2023)
22 Apply the shortest-augmenting path algorithm to find a maximum flow and a
minimum cut in the following network.(Nov 2023)

23. Write pseudo code for maximum-matching algorithm. Apply the maximum-matching
algorithm to the following bipartite graph.

Analyze the time complexity of maximum-matching algorithm. (Nov 23)

COPING WITH THE LIMITATIONS OF ALGORITHM POWER
Lower - Bound Arguments - P, NP, NP- Complete and NP Hard Problems. Backtracking – n-
Queen problem - Hamiltonian Circuit Problem – Subset Sum Problem. Branch and bound –
LIFO Search and FIFO search - Assignment problem – Knapsack Problem – Travelling
Salesman Problem - Approximation Algorithms for NP-Hard Problems – Travelling
Salesman problem – Knapsack problem.
UNIT-V / PART-A
1. What is lower bound and trivial lower bound?
Given a class of algorithms for solving a particular problem, a lower bound
indicates the best possible efficiency any algorithm from this class can have.
A trivial lower bound is based on counting the number of items in the problem’s
input that must be processed and the number of output items that need to be
produced.

St. Joseph’s College of Engineering Page 32 of 38

CS1401- Design and Analysis of Algorithms Department of CSE, IT, ADS and AML 2023-2024
2. What is information-theoretic lower bound?
An information-theoretic lower bound is usually obtained through a mechanism of
decision trees. This technique is particularly useful for comparison-based algorithms for
sorting and searching. Specifically:
 Any general comparison-based sorting algorithm must perform at least log2 n!_ ≈
n log2 n key comparisons in the worst case.
 Any general comparison-based algorithm for searching a sorted array must perform
at least log2(n + 1) key comparisons in the worst case
3. Draw decision tree for finding minimum of 3 numbers.

4. Differentiate between tractable and intractable problems.

Problems that can be solved in polynomial time are called tractable, and problems
that cannot be solved in polynomial time are called intractable.

5. Define Class P problems. (Nov 22)

Class P is a class of decision problems that can be solved in polynomial time by
(deterministic) algorithms. This class of problems is called polynomial.
6. Differentiate between undecidable and decidable problems.
Some decision problems cannot be solved at all by any algorithm. Such problems
are called undecidable, as opposed to decidable problems that can be solved by an
algorithm. A famous example of an undecidable problem is the halting problem

7. State halting problem

Given a computer program and an input to it, determine whether the program
will halt on that input or continue working indefinitely on it.

8. List some important problems, for which no polynomial-time algorithm has been
found
 Define Hamiltonian circuit problem
 Traveling salesman problem
 Knapsack problem
 Partitioning problem
 Bin packing problem
 Graph coloring problem
 Integer linear programming problem.
9. Define nondeterministic algorithm
A nondeterministic algorithm is a two-stage procedure that takes as its input an
instance I of a decision problem and does the following.
 Nondeterministic (“guessing”) stage: An arbitrary string S is generated that can be
thought of as a candidate solution to the given instance I
 (Deterministic (“verification”) stage: A deterministic algorithm takes both I and S as
its input and outputs yes if S represents a solution to instance I. (If S is not a solution
to instance I , the algorithm either returns no or is allowed not to halt at
all.)

St. Joseph’s College of Engineering Page 33 of 38

CS1401- Design and Analysis of Algorithms Department of CSE, IT, ADS and AML 2023-2024
10. Define Class NP problems. (May 2023)
Class NP is the class of decision problems that can be solved by nondeterministic
polynomial algorithms. This class of problems is called nondeterministic polynomial.

11. What do you mean by polynomially reducible?

A decision problem D1 is said to be polynomially reducible to a decision problem
D2, if there exists a function t that transforms instances of D1 to instances of D2 such that:
 t maps all yes instances of D1 to yes instances of D2 and all no instances of D1 to
no instances of D2
 t is computable by a polynomial time algorithm
12. Define NP complete and NP-hard. (May 19, Apr 22)
A decision problem D is said to be NP-complete if:
 it belongs to class NP
 every problem in NP is polynomially reducible to D
A problem is NP-hard if all problems in NP are polynomial time reducible to it, even
though it may not be in NP itself.
13. When a problem is said to be NP hard? (Dec 19)
A problem is said to be NP-hard if an algorithm for solving it can be translated into
one for solving any other NP-problem. Any given problem X acts as NP-Hard only if there
exists a problem Y that is NP-Complete. Here, problem Y becomes reducible to
problem X in a polynomial time.
14. Draw the relation among P, NP, NP-hard and NP-complete

15. Differentiate between NP hard and NP complete problems. (Dec 20,Nov 23)
Parameters NP hard NP complete
Meaning and One can only solve an NP- Any given problem X acts as NP-
Definition Hard Problem X only if an NP- Complete when there exists an NP
Complete Problem Y exists. It problem Y- so that the problem Y gets
then becomes reducible to reducible to the problem X in a
problem X in a polynomial polynomial line.
time.
Presence in NP The NP-Hard Problem does not For solving an NP-Complete Problem,
have to exist in the NP for the given problem must exist in both
anyone to solve it. NP-Hard and NP Problems.
Decision This type of problem need not This type of problem is always a
Problem be a Decision problem Decision problem (exclusively).
Example Circuit-satisfactory, Vertex The determination of the Hamiltonian
cover, Halting problems, etc., cycle in a graph, the determination of
are a few examples of NP- Hard the satisfaction level of a Boolean
Problems formula, etc

St. Joseph’s College of Engineering Page 34 of 38

CS1401- Design and Analysis of Algorithms Department of CSE, IT, ADS and AML 2023-2024
16. What is backtracking? (Nov 21)
The principal idea of backtracking is to construct solutions one component at a time
and evaluate such partially constructed candidates as follows. If a partially constructed
solution can be developed further without violating the problem’s constraints, it is done
by taking the first remaining legitimate option for the next component. If there is no
legitimate option for the next component, no alternatives for any remaining component
need to be considered. In this case, the algorithm backtracks to
replace the last component of the partially constructed solution with its next option.
17. How can you implement backtracking?
It is convenient to implement backtracking by constructing a tree of choices being
made, called the state-space tree. Its root represents an initial state before the search for a
solution begins. The nodes of the first level in the tree represent the choices made for the
first component of a solution, the nodes of the second level represent the choices for the
second component, and so on.
18. What is promising and nonpromising nodes in state space tree? (Nov 21)
A node in a state-space tree is said to be promising if it corresponds to a partially
constructed solution that may still lead to a complete solution; otherwise, it is called
nonpromising. Leaves represent either nonpromising dead ends or complete solutions
found by the algorithm.
19. Define Hamiltonian circuit problem. (May 19, Dec 19,Nov 23)
Determine whether a given graph has a Hamiltonian circuit (a path that starts and ends
at the same vertex and passes through all the other vertices exactly once) is known as
Hamiltonian Circuit problem.
20. How a state-space tree for a backtracking algorithm is constructed?
In the majority of cases, a state-space tree for a backtracking algorithm is constructed
in the manner of depth first search. If the current node is promising, its child is generated
by adding the first remaining legitimate option for the next component of a solution, and
the processing moves to this child. If the current node turns out to be nonpromising, the
algorithm backtracks to the node’s parent to consider the next possible option for its last
component; if there is no such option, it backtracks one more level up the tree, and so on.
Finally, if the algorithm reaches a complete solution to the problem, it either stops (if just
one solution is required) or continues searching for other possible
solutions.
21. State n-queens problem. (Nov 22)
The problem is to place n-queens on an n × n chessboard so that no two queens
attack each other by being in the same row or in the same column or on the same
diagonal.
22. State subset-sum problem.
Subset-sum problem: find a subset of a given set A = {a1, . . . , an } of n positive
integers whose sum is equal to a given positive integer d. For example, for A = {1, 2, 5, 6,
8} and d = 9, there are two solutions: {1, 2, 6} and {1, 8}. Some instances of this problem
may have no solutions.
23. What is branch and bound algorithm?
Branch-and-bound is an algorithm design technique that enhances the idea of
generating a state-space tree with the idea of estimating the best value obtainable from a
current node of the decision tree: if such an estimate is not superior to the best solution
seen up to that point in the processing, the node is eliminated from further consideration.

St. Joseph’s College of Engineering Page 35 of 38

CS1401- Design and Analysis of Algorithms Department of CSE, IT, ADS and AML 2023-2024
24. List the two additional items requires for branch-and-bound compared to backtracking.
Compared to backtracking, branch-and-bound requires two additional items:
 a way to provide, for every node of a state-space tree, a bound on the best value of
the objective function on any solution that can be obtained by adding further
components to the partially constructed solution represented by the node
 the value of the best solution seen so far

25. What is LC search and how it is efficient from other search methods in branch and
bound algorithms? (Dec 20)
Branch and Bound can be solved using FIFO, LIFO and LC strategies. The least cost
(LC) is considered the most intelligent as it selects the next node based on a Heuristic
Cost Function. It picks the one with the least cost.
27. Give the purpose of lower bound. (Apr 22)
Lower bound is an estimate on a minimum amount of work needed to solve a given
problem. (In branch and bound, a lower bound is a value smaller than or equal to the
smallest value in a set)
28. What is approximation algorithm?
Approximation algorithms are often used to find approximate solutions to
difficult problems of combinatorial optimization. The performance ratio is the principal
metric for measuring the accuracy of such approximation algorithms.
29 Provide the possible solutions in 4-queen’s problem. (May 2023)

UNIT-V / PART-B
1. i) Prove that any algorithm that searches need to necessarily do Ω (lg n) comparisons.
(May 19)
ii) Prove that any algorithm that sorts by comparison, requires Ω (n log n) time. (May 19)
2. Write an algorithm for subset sum and explain with an example. (May 19)
3. Write the algorithm for sum of subsets problem using backtracking technique. Illustrate
the algorithm for the instance n = 6, M= 30 and W = (5, 10, 12, 13, 15, 18). Draw possible
state space tree. (Dec 20)
4. Explain backtracking search for a solution to the four-queen problem, to find the first and
second solution.
5. Elaborate how backtracking technique can be used to solve the n-queens problem.
Explain with an example. (Dec 19)
6. Apply the branch-and-bound algorithm to solve the traveling salesman problem for the
following graph: (Dec 21)

St. Joseph’s College of Engineering Page 36 of 38

CS1401- Design and Analysis of Algorithms Department of CSE, IT, ADS and AML 2023-2024
7. What are the general approaches exit for branch and bound algorithms? Also explain the
data structure need for storing live nodes in each approach with suitable example. (Dec
20)
8. Explain branch and bound method to solve the following assignment problem. (Apr 22)
Job 1 Job 2 Job 3 Job 4
Person 1 9 2 7 8
Person 2 6 4 3 7
Person 3 5 8 1 8
Person 4 7 6 9 4
9. Solve the TSP using branch and bound technique. (Dec 20)
A B C D
A α 12 5 7
B 11 α 13 6
C 4 9 α 18
D 10 3 2 α
10. Write the algorithm for solving 0/1 knapsack problem using LC branch and bound and
solve the knapsack instance; n = 4; (p1, p2, p3, p4) = (10, 10, 12, 18); (w1, w2, w3, w4) = (2,
4, 6, 9) and M= 15, using LCBB, Draw the state space tree. (Dec 20)

11. Solve the following instance of the knapsack problem by the branch-and bound
algorithm: (Nov 21)

12. Solve TSP problem using branch and bound and approximation design techniques.
Compare the results (Apr 22)

13. Write an algorithm to solve the Travelling salesman problem and prove that it is a 2-time
approximation algorithm. (May 19)

14. Outline the steps to find an approximate solution to NP-hard optimization problem using
approximation algorithms with an example. (Dec 19)
15. Prove that TSP problem is NP complete, assuming that Hamiltonian problem is NP
complete. (Dec 20)
St. Joseph’s College of Engineering Page 37 of 38
CS1401- Design and Analysis of Algorithms Department of CSE, IT, ADS and AML 2023-2024
17. Describe the backtracking solution to solve 4-queens problem. (Apr 22)
16. Explain the operations of approximate vertex cover and give an example of a graph for
which APPROX-VERTEX-COVER always yields a suboptimal solution. (Dec 20)
Apply the nearest-neighbor algorithm and Multifragmenting-heuristic algorithm to the
instance defined by the intercity distance matrix below. Start the algorithm at the first city,
assuming that the cities are numbered from 1 to 5.

Compute the accuracy ratio of this approximate solution. Compute the accuracy ratio of
this approximate solution using twice-around the tree algorithm. (May 2023)
17. Write an algorithm of subset sum problem. Draw the complete state-space tree of the
backtracking algorithm applied to the instance: W = (5,7,10,12,15,18,20) and M = 35 of the
subset-sum problem. (May 2023)

18. Explain approximation algorithm for knapsack problem in detail.

19. Apply the twice around the tree algorithm and Christofides algorithm to the following
graph (Nov 21)

20. State subset-sum problem. Solve the following subset-sum problem using backtracking
method. Draw the complete state space tree. A={3,5,6,7} and d=15 (Nov 22)
21. Explain approximation algorithms for travelling salesman problem with your own
example. (Nov 22)
22. Solve the following instance of the travelling salesman problem by branch and bound
method.(Nov 23)

23. Apply backtracking to solve the following instance of the subset sum problem:A={1,3,4,5}
and d=11 and explain it with an algorithm.(Nov 23)

St. Joseph’s College of Engineering Page 38 of 38