CS8451- DESIGN AND ANALYSIS OF ALGORITHMS IV Semester CSE

DHANALAKSHMI COLLEGE OF ENGINEERING

Tambaram, Chennai

Department of Computer Science and Engineering

CS8451 – Design and Analysis of Algorithms

Year / Sem : II / IV
2 Marks Q & A

UNIT - III

Department of Computer Science and Engineering Page 1

CS8451- DESIGN AND ANALYSIS OF ALGORITHMS IV Semester CSE

UNIT- III
DYNAMIC PROGRAMMING AND GREEDY TECHNIQUE
PART A

1. State the principle of optimality. [N/D  18]

The principle of optimality states that “In an optimal sequence of decisions or choices,
each subsequence must also be optimal”.

2. What is the use of Floyd’s algorithm? [N/D  17]

The Floyd’s algorithm is used to find the shortest path from any vertex to any other
vertices. It is also called “all pair shortest path algorithm”.

3. List the memory functions used under Dynamic Programming. [A/M  15]
Memory functions used under Dynamic Programming
a) Memory function for Binomial Coefficient is
C(n, k) = C(n1, k1) + C(n1, k), where C(n, 0)=1 and C(n, n)=1.
b) Memory function for Knapsack Problem is
table[i, j] = maximum{ table[i1, j], Vi + table [i1, jWi] if j >= Wi
or table[i1, j] if j < Wi }.

4. State the general principle of Greedy algorithm. [A/M  17]

General principle of Greedy algorithm
a) In the Greedy technique, the solution is constructed through a sequence of steps,
each step expanding partially constructed solution obtained so far, until a
complete solution to the problem is reached.
b) At each step, the choice of feasible solutions is made. (i.e., feasible, irrevocable
and locally optimum)
c) From the set of feasible solutions, the optimal solution is selected as the solution
to the problem.

5. What is meant by Dynamic Programming? [A/M  17]

Dynamic programming is a technique for solving problems with overlapping subproblems.
In this method, each subproblem is solved only once. The result of each subproblem is
recorded in a table from which the solution can be obtained for the original problem.

6. What is meant by multistage graph?

A multistage graph G = (V, E) is a directed graph. In this graph, all the vertices are
partitioned into ‘K’ stages where K >= 2. The multistage graph problem is a problem of
finding the shortest path from source to sink. The cost of a path from source (s) to
sink (t) is the sum of the cost of the edge.

Department of Computer Science and Engineering Page 2

CS8451- DESIGN AND ANALYSIS OF ALGORITHMS IV Semester CSE

7. Distinguish between Greedy method and Dynamic Programming. [M/J  12]

S. No. Greedy Method Dynamic Programming
1 Greedy method is used for Dynamic programming is also used
obtaining optimum solution. for obtaining optimum solution.
2 In this method, a set of feasible There is no special set of feasible
solutions are obtained and then solutions.
picks up the optimum solution.
In this method, the optimum It considers all possible sequences
3 selection is generated without in order to obtain the optimum
revising previously generated solution.
solutions.
4 In this method, there is no It generates optimal solution by
guarantee for optimum solution. using principle of optimality.

8. What are the drawbacks of Greedy algorithm? [M/J  12]

Drawbacks of Greedy algorithm
a) Greedy method is comparatively efficient than Divide and Conquer but there is
no guarantee of getting optimum solution.
b) In Greedy method, the optimum selection is generated without revising
previously generated solutions.

9. List the advantages of Dynamic Programming. [M/J  14]

Advantages of Dynamic Programming
a) Idea of reuse i.e., solutions of the subproblems can be reused rather than
recomputing them.
b) Solutions are globally optimum.
c) It is a valuable tool for computing both exact and approximate solutions.

11. Define  Single Source Shortest Path Problem [M/J  16]

Single Source Shortest Path Problem is defined as a problem in which there exists a
source
vertex from which the shortest path to all other vertices is obtained.

12. What is the purpose of Huffman’s algorithm?

The purpose of Huffman’s algorithm is to find the codeword for the set of given strings.
This codeword is also known as Huffman code.

13. What is meant by Spanning tree? [M/J  18]

Spanning tree of a graph G is a subgraph which is basically a tree and it contains all the
vertices of G containing no circuit.

14. What is meant by Minimum Spanning Tree?

A Minimum Spanning Tree (MST) of a weighted connected graph G is a spanning tree
with minimum or smallest weight.

Department of Computer Science and Engineering Page 3

CS8451- DESIGN AND ANALYSIS OF ALGORITHMS IV Semester CSE

15. What is meant by 0/1 Knapsack Problem? [N/D  12]

The 0/1 Knapsack Problem is the problem of picking up the most valuable objects to fill
knapsack to its capacity. It must satisfy the following objective function
Maximize ∑pixi where i = 1 to n subject to constraint ∑WiXi <= W where i = 1 to n.

16. Distinguish between Prim’s algorithm and Kruskal’s algorithm.

S. No. Prim’s algorithm Kruskal’s algorithm
1 Prim’s algorithm initializes with Kruskal’s algorithm initializes with
node edges
2 In Prim’s algorithm, the next In Kruskal’s algorithm, the minimum
node is always selected from weight edge is selected independent of
previously selected node previously selected edge.
(adjacent node).
3 Time complexity is O(V2) Time complexity is O(E log E)

17. Define – Optimal Solution

Optimal Solution is defined as the best choice solution selected from the set of feasible
solutions. This solution can be minimum or the maximum value of the solution.

18. What is meant by Transitive Closure?

The Transitive Closure of a directed graph with ‘n’ vertices can be defined as the n x n
boolean matrix T = {tij} in which the element in the ith row and jth column is 1 if there
exists a nontrivial path from ith vertex to jth vertex. Otherwise tij is 0.

19. What is meant by objective function?

A feasible solution is one that either maximizes or minimizes a given function. This
function is called objective function.
Example: In 0/1 Knapsack Problem, Maximize ∑PiXi where i = 1 to n is an objective
function.

20. What are the general characteristics of Greedy algorithm?

General characteristics of Greedy algorithm
a) Greedy choice property
b) Optimal substructure property

21. What are the two types of encoding in Huffman code?

Types of encoding in Huffman code

Department of Computer Science and Engineering Page 4

CS8451- DESIGN AND ANALYSIS OF ALGORITHMS IV Semester CSE

a) Fixed-length encoding
b) Variable-length encoding

22. What is meant by Huffman tree?

Huffman tree is a binary tree that minimizes the weighted path length from the root to the
leaves of predefined weights.

23. Devise an algorithm to make for 1655 using the Greedy strategy. The coins available
are {1000, 500, 100, 50, 20, 10, 5}. [N/D  17]
Algorithm Coin_Selection
{
while (there are more coins && the instance is not solved)
{
select the large coin
if (total exceeds amount)
reject coin
else (total < amount)
add coin to the change
else if (total = amount)
declare solution
}
}

PART B

1. Discuss about the algorithm and pseudo code to find the minimum spanning tree using
prim’s algorithm. Find the minimum spanning tree for the graph shown below and discuss
about the efficiency of the algorithm.

Aspanning 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.

Department of Computer Science and Engineering Page 5

CS8451- DESIGN AND ANALYSIS OF ALGORITHMS IV Semester CSE

The minimum spanning tree problem is the problem of finding a minimum spanning tree for a
given weighted connected graph.

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 O(|V |2).
The solution for the above graph is ie Total weight = 2+3+1 =6.

2. Define Spanning tree. Discuss the design steps in kruskal algorithm to construct
minimum spanning tree with example.
Aspanning 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

Department of Computer Science and Engineering Page 6

CS8451- DESIGN AND ANALYSIS OF ALGORITHMS IV Semester CSE

3. Write the Huffman’s algorithm. Construct the Huffman tree for the following data
Character A B C D E _
Probability 0.5 0.35 0.5 0.1 0.4 0.2

Algorithm Huffman(c)
Huffman’s algorithm
{
Step 1 Initialize n one-node trees and label them with the
C=|c| symbols of the alphabet given. Record the frequency of each
Q=c symbol in its tree’s root to indicate the tree’s weight. (More
generally, the weight of a tree will be equal to the sum of the
For i1 to n-1
frequencies in the tree’s leaves.)

Department of Computer Science and Engineering Page 7

Step 2 Repeat the following operation until a single tree is
obtained. Find two trees with the smallest weight , Make
them the left and right subtree of a new tree and record the
CS8451- DESIGN AND ANALYSIS OF ALGORITHMS IV Semester CSE

Do
{
Tempget_node()
Left[temp] =Get_min(Q)
Right[temp]= Get_min(Q)
A=left[temp]
B=right[temp]
F[temp] f|a| + f|b|
Insert(Q, temp)
}
Return Get_min(Q) The resultant code for the above Character
D – 1100 _ - 1101 B – 111 E – 00 A – 01 C – 10

4. Solve the all-pairs shortest path problem for the digraph

Department of Computer Science and Engineering Page 8

CS8451- DESIGN AND ANALYSIS OF ALGORITHMS IV Semester CSE

5. Explain the Multistage graph with example

A multistage graph G = (V, E) is a directed graph where vertices are partitioned into k (where k
> 1) number of disjoint subsets S = {s1,s2,…,sk} such that edge (u, v) is in E, then u Є si and v Є s1
+ 1 for some subsets in the partition and |s1| = |sk| = 1.

The vertex s Є s1 is called the source and the vertex t Є sk is called sink. G is usually assumed to
be a weighted graph. In this graph, cost of an edge (i, j) is represented by c(i, j). Hence, the cost
of path from source s to sink t is the sum of costs of each edges in this path.

The multistage graph problem is finding the path with minimum cost from source s to sink t.

Example

Consider the following example to understand the concept of multistage graph.

According to the formula, we have to calculate the cost (i, j) using the following steps

Step-1: Cost (K-2, j)

In this step, three nodes (node 4, 5. 6) are selected as j. Hence, we have three options to choose
the minimum cost at this step.

Cost(3, 4) = min {c(4, 7) + Cost(7, 9),c(4, 8) + Cost(8, 9)} = 7

Cost(3, 5) = min {c(5, 7) + Cost(7, 9),c(5, 8) + Cost(8, 9)} = 5

Cost(3, 6) = min {c(6, 7) + Cost(7, 9),c(6, 8) + Cost(8, 9)} = 5

Step-2: Cost (K-3, j)

Department of Computer Science and Engineering Page 9

CS8451- DESIGN AND ANALYSIS OF ALGORITHMS IV Semester CSE

Two nodes are selected as j because at stage k - 3 = 2 there are two nodes, 2 and 3. So, the value
i = 2 and j = 2 and 3.

Cost(2, 2) = min {c(2, 4) + Cost(4, 8) + Cost(8, 9),c(2, 6) +

Cost(6, 8) + Cost(8, 9)} = 8

Cost(2, 3) = {c(3, 4) + Cost(4, 8) + Cost(8, 9), c(3, 5) + Cost(5, 8)+ Cost(8, 9), c(3, 6) + Cost(6,
8) + Cost(8, 9)} = 10

Step-3: Cost (K-4, j)

Cost (1, 1) = {c(1, 2) + Cost(2, 6) + Cost(6, 8) + Cost(8, 9), c(1, 3) + Cost(3, 5) + Cost(5, 8) +
Cost(8, 9))} = 12

c(1, 3) + Cost(3, 6) + Cost(6, 8 + Cost(8, 9))} = 13

Hence, the path having the minimum cost is 1→ 3→ 5→ 8→ 9.

6. Explain in detail, How the Knapsack problem is solved by dynamic programming?

Knapsack problem: Given n items of known weights w1, . . . , wn and values v1, . . . , vn and a
knapsack of capacity W, find the most valuable subset of the items that fit into the knapsack.

Our goal is to find F(n, W), the maximal value of a subset of the n given items that fit into the
knapsack of capacity W, and an optimal subset itself.

Department of Computer Science and Engineering Page 10

CS8451- DESIGN AND ANALYSIS OF ALGORITHMS IV Semester CSE

7. Explain the binary search algorithm in detail.

Binary search can be performed on a sorted array. In this approach, the index of an element x is
determined if the element belongs to the list of elements. If the array is unsorted, linear search is
used to determine the position.
In this algorithm, we want to find whether element x belongs to a set of numbers stored in an
array numbers[]. Where l and r represent the left and right index of a sub-array in which
searching operation should be performed.

Algorithm: Binary-Search(numbers[], x, l, r)
if l = r then
return l
else
m := ⌊(l + r) / 2⌋
if x ≤ numbers[m] then
return Binary-Search(numbers[], x, l, m)
else
return Binary-Search(numbers[], x, m+1, r)

Analysis
Binary search produces the result in O(log n) time. Let T(n) be the number of comparisons in

worst-case in an array of n elements. Hence, T(n)={0T(n2)+1ifn=1otherwise

Using this recurrence relation T(n)=logn, Therefore, binary search uses O(logn)time.

Department of Computer Science and Engineering Page 11

CS8451- DESIGN AND ANALYSIS OF ALGORITHMS IV Semester CSE

In this example, we are going to search element 63.

8. How the Binomial coefficient can be computed by using dynamic programming?

1) Optimal Substucture
The value of C(n, k) can be recursively calculated using following standard formula for Binomial
Coefficients.
C(n, k) = C(n-1, k-1) + C(n-1, k)
C(n, 0) = C(n, n) = 1

2) Overlapping Subproblems
It should be noted that the above function computes the same subproblems again and again. See
the following recursion tree for n = 5 an k = 2. The function C(3, 1) is called two times. For large
values of n, there will be many common subproblems.
C(5, 2)
/ \
C(4, 1) C(4, 2)
/ \ / \
C(3, 0) C(3, 1) C(3, 1) C(3, 2)
/ \ / \ / \
C(2, 0) C(2, 1) C(2, 0) C(2, 1) C(2, 1) C(2, 2)
/ \ / \ / \
C(1, 0) C(1, 1) C(1, 0) C(1, 1) C(1, 0) C(1, 1)

Since same suproblems are called again, this problem has Overlapping Subproblems property. So
the Binomial Coefficient problem has both properties of a dynamic programming problem.

Department of Computer Science and Engineering Page 12

CS8451- DESIGN AND ANALYSIS OF ALGORITHMS IV Semester CSE

Department of Computer Science and Engineering Page 13