CMR Institute of Technology, Bangalore

Department(s): INFORMATION SCIENCE AND ENGINEERING

Semester: IV Section(s): A & B
DESIGN & ANALYSIS OF ALGORITHMS 10CS43 Lectures/week: 05
Course Instructor(s): Asst.Prof PRIYANKA.R
Course duration: 27 Jan. 2014 – 23 May 2014

Unit 1 : Introduction
1. What is an algorithm? Write step by step procedure to write an algorithm.
2. What are the properties of an algorithm? Explain with an example.
3. Define asymptotic notations for worst case, best case and average case time complexities.
Give examples.(OR) Explain all asymptotic notations used in algorithm analysis.(OR)
Explain in brief the basic asymptotic efficiency classes.(OR) Explain the worst-case, best-
case and average case efficiencies of an algorithm with help of an example.

4. Explain the general plan for analyzing the efficiency of a recursive algorithm.
5. Explain the method of comparing the order of the growth of 2 functions using limits.
Compare order of growth of (i) log2 n and sqrt(n) ii) (log2 n)2 and log2 n2 .

6. Discuss the general plan for analyzing efficiency of non recursive algorithms.
7. Write an algorithm to compute n! recursively. Set up a recurrence relation for the
algorithm's basic operation count and solve it.

8. Consider the following algorithm

Algorithm Enigma (A[0··n -1, 0..n-1])
for i = 0 to n-2 do
for j=i+1 to n-1 do
if A[i,j]Not equal to A[j,i]
return false
end for
end for
return true
end algorithm

i) What does this algorithm compute?

ii) What is its basic operation
iii) How many times is the basic operation executed?

9. Find GCD (60, 24) by applying Euclid's formula. Estimate the number of times
computation is done in Euclid's method and in an algorithm based on checking
consecutive integers from min (m, n) down to gcd (m, n).

10. Write 3 different types of procedures for computing GCD of 2 numbers and analyze
the efficiency.

1
 11. Write the algorithm to compute the sum of n numbers and indicate
(a) Natural size metric for its inputs
(b) Its basic operation
(c) Whether the basic operation count can be different for inputs of the same size.

12. Consider the following recursive algorithm for computing the sum of the first n cubes.

S (n) = 13 + 23 + 33 + .......... + n3
Algorithm S (n)
if(n = 1) return 1
else return (S(n-1)+n*n*n)
end algorithm
Design and Analysis of Algorithms 10CS43
Set up and solve a recurrence relation for the number of times the algorithm's basic
operation is executed.

13. What is brute force method? Explain sequential search algorithm with an example. Analyze
its efficiency.

14. Write an algorithm for selection sort method. Show that its worst case time complexity is
O (n2).

15. Give an algorithm for selection sort. If C (n) denotes the no of times the algorithm is
executed (n denotes input size), obtain an expression for C (n).

16. Sort the following list using bubble sort method 66,55,44,33,22,11 in ascending
order.

17. If t1(n) € 0 (gr (n)) and t2 (n) e 0(gz (n)), prove that t1 (n) + t2 (n) e 0(max {gr (n), g :( n)}).

18. If M(n) denotes the, number of moves in tower of Hanoi puzzle when n disks are involved,
give a recurrence relation for M(n) and solve this recurrence relation

19. With a suitable example explain the significance of Order of Growth in analyzing the
algorithm efficiency

20. What is a “Brute force “method? Under what condition does the method become desirable?
21. a. Using bubble sort algorithm arrange the letters of the word “QUESTION” in
alphabetical order
b. Explain brute force method for algorithm design and analysis. Explain the brute
force string matching algorithm with its efficiency.

Unit 2 : Divide And Conquer

22. Explain the general concept of divide - and conquer method. Show how binary search
problem can be solved using the same method, find its average case efficiency.

23. Define Master theorem. Compute the time complexity for the following recurrence equation
using the same.
i) T (n) = 4T (nl2) + n, T(1) = 1; ii) T(n) = 4T (nl2) +n2, T(1) = 1
iii) T (n) = 4T (nl2) +n3, T (1) = 1; iv) T (n) = 2T (nl2) + Cn, T (1) = 0
2
 24. Give the general divide and conquer recurrence and explain the same. Give the Master’s
theorem.

25. Discuss the merge sort algorithm with recursive tree and its efficiency. Apply the
same algorithm to sort the list {4,6,1,3,9,5}

26. Write the quick sort algorithm. Analyze its efficiency. Apply the algorithm to sort the
list 4, 1, 6, 3, 9, 2, 7, 5 .Derive worst case complexity of it.

27. Using quick sort algorithm arrange the letters of the word “Example” and “Question” in
alphabetical order.

28. Write the algorithm for binary search and find the average case efficiency.
29. If ne [2k-r.2k), prove that binary search algorithm makes at most K element comparisons
for ' a successful search and either K - I or K comparisons for an unsuccessful search.

30. Give an algorithm (recursive) for merge sort.

31. Consider the numbers given below. Show how partitioning algorithm of quick sort will
place106 in its correct position. Show all the steps clearly.
106 117 128 134 141 91 84 63 42

32. Derive the time complexity for defective chess board.

33. Consider the set of 14 elements in array list:-
15,16,0,7,9,23,54,82,101,112,125,131,142,151. When binary search is applied on these
elements, find the elements which required maximum number of comparisons. Also
determine the average number of key comparisons for successful and unsuccessful search.

34. Explain divide and conquer technique. Write the algorithm for binary search and find
average case efficiency.
What is stable algorithm? Is quick sort stable? Explain with an example.

Unit 3 : The Greedy Method

35. What is greedy technique? Explain in detail the general method.

36. What is spanning tree? What is minimum spanning tree?
37. Justify the statement “Prim’s algorithm always yields minimum cost spanning tree”. Give
the prim’s algorithm and discuss its time complexity.
38. Give kruskal’s algorithm and discuss its time complexity.
39. Give the Dijkstra’s algorithm. What is its complexity? Discuss with a simple example.
40. Use the kruskal’s algorithm to solve the min cost spanning tree for the graph given
41. Use the prim’s algorithm to solve the min cost spanning tree for the graph given
42. Solve the following instances of the single source shortest path problem with vertex ‘a’ as
source.

3
 a.Solve the following knapsack problem with given capacity W= 5 using Greedy method.

item weight value

1 2 $12
2 1 $10
3 3 $20
4 2 $15

b.Solve the following knapsack problem with given capacity W= 10 using Greedy method

item weight value

1 4 $40
2 7 $42
3 5 $25
4 3 $12

43. Obtain the optimal solution for the job sequencing problem with deadlines where n=4(no of
jobs), profits (p1,p2,p3,p4) = (100,10,15,27) and deadlines (d1,d2,d3,d4) = (2,1,2,1)

44. Let J be at set of K Jobs and Sigma=i1, i2, i3, ….., ik be a permutation of jobs in J such that
di1≤
di2≤ di3≤……. di1≤ dik. Prove that J is a feasible solution if and only if the jobs in J can be
Processed in the order sigma without violating any deadline.

45. Define i) Optimal solution ii) Feasible solution. Will greedy method yield an optimal
solution always?

Unit 4 : Dynamic Programming

46. Explain Dynamic programming.
47. Write the formula to find the shortest path using Floyd's approach. Use Floyd's method to
solve the below all-pairs shortest paths problem.
0 ∞ 3 ∞
2 0 ∞ ∞
∞7 0 1
6 ∞∞ 0
48. State all pair shortest path algorithm. Solve the all pairs shortest path problem for the
diagraph with the weight matrix.
0 2 ∞ 1 8
6 0 3 2 ∞
∞∞ 0 4 8
∞∞ 2 0 3
3∞∞ ∞ 0
49. Explain Warshall’s Algorithm in detail.

4
 50. Using dynamic programming, solve the following knapsack instance:
n=3,[w1,w2,w3]= [1, 2,2] and [p1,P2,P3] =[18, 16,6] and M=4

51. Solve the following traveling sales person problem, using dynamic programming
52. Explain the difference between DFS and BFS. Solve topological sorting problem using DFS
algorithm, with an example

53. List out the difference between divide and conquer and dynamic programming.
54. Using Warshall's algorithm, obtain the transitive closure of the matrix given below:
0000
0001
0000
1010
55. Outline an exhaustive search algorithm to solve traveling salesman problem

Unit 5 : Decrease & Conquer Approaches, Space-Time Tradeoffs

56. Discuss about major variants of decrease - and – conquer r method. Give one example for
each.

57. Show how DFS method can be used to conduct topological sorting.
58. Write depth first search and breadth first search algorithm.
59. Briefly explain how breadth first search can be used to check connections of a graph and
also to find the number of components in a graph.

60. Explain the difference between DFS and BFS. Solve topological sorting problem using DFS
Algorithm, with an example.

61. Apply insertion sort to sort the list E,X,A,M,P,L,E in alphabetical order.
62. Write Horspool's algorithm. Apply Horspool algorithm to search for the pattern BAOBAB
in the text BESS_ KNEW _ABOUT_BAOBABA. Also, find the total number of
comparisons made.

63. Write an algorithm for comparison counting and show how comparison counting
method sorts the list 45,2,19,10,33,22,1,23

64. Show how insertion sort arranges the following members in increasing order.
61,28,9,85,34

65. Give algorithms for the following: a) Comparison counting b) Distribution counting
66. What are the three major variations of decrease and conquer technique explain each with
an example.

67. Write an algorithm to find the shortest path between any two given vertices using
DFS method (BFS Method).

5
 68. What do you mean by topological sort? Give its applications. Explain source removal
method to find topological sorting.

69. Traverse the graph using DFS & construct the corresponding DFS tree. Give the order in
which vertices are reached for the first time(pushed on to stack) and the order in which
vertices become dead ends(popped off stack).Also mention the tree edges and back edges of
the graph

Unit 6 : Limitations of algorithmic power and coping with them

70. Explain lower bound arguments, its advantages. What is meant by trivial lower bounds and
what are its limitations.

71. What are decision trees? Explain with example, how decision trees are used in sorting
algorithms.

72. Explain the concepts of P, NP, and NP – complete problems. (OR) Write short notes on P,
NP and NP-complete problems (OR) Define P, NP and NP complete problems

73. Define the following: i) Tractable Problems, ii) Class p, iii) Class NP, iv) Polynomial
Reduction, v) NP Complete

74. Draw the decision tree for the 3-elements insertion sort.
75. What are the challenges of Numerical Algorithms
76. Explain approximation algorithm for NP- hard problem in general.

Unit 7 : Coping with limitations of algorithmic power

77. Define 1.backtracking 2. Implicit constraints 3. Explicit constraints 4. State/solution
5.state/solution space 6.state /solution space tree

78. Draw the state – space tree to generate solutions to 4 – Queen’s problem. (OR) Explain how
backtracking is used for solving 4- queens problem. Show the state space tree.

79. Explain approximation algorithms for NP-hard problems in general. Also discuss
Approximation algorithms for knapsack problem.

80. State subset sum Problem. Use backtracking, obtain a solution to the subset sum problem
by taking (i) S={6, 8, 2, 14} and d=16. (ii) S={5,10,12,13,15,18} d=30

81. What is branch – and - bound algorithm? How it is different from backtracking?
82. Write the steps and apply nearest neighbor approximation algorithm on the TSP
problem with the starting vertex a, and calculate the accuracy ratio of approximation.

83. Write short notes on: a) Travelling Sales person Problem b) Input Enhancement in
String Matching c) Decision Tree. d) Challenges of numerical algorithms.

6
 84. Solve the following instance of Assignment problem using Branch-Bound technique

Job1 Job2 Job3 Job4

9 2 7 8
6 4 3 7
5 8 1 8
7 6 9 4
85. Solve the knapsack problem using branch and bound given the following data: M=10 total
item=4, Weights= 4,7,5,3 Value = 40,42,25,12 value/weight = 10,6,5,4

86. Apply branch and bound algorithm to solve the travelling salesman problem for the
following graph.

Unit 8 : PRAM Algorithm

87. What is prefix computation problem? Give algorithm for prefix computation which uses
i) n processors ii) n/log n processors. Obtain the time complexities of these algorithms.

88. For an n x n matrix M with nonnegative integer coefficients, define M’ and give an
algorithm for computing M’. Prove that M’ can be computed from nxn matrix M in O(logn)
time using n3+e common CRCW PRAM processors for any fixed e>0.

89. What are the different computation models? Discuss in detail.

90. Let the input to the prefix computation problem be 5, 12, 8, 6, 3, 9, 11, 12, 5, 6, 7,
10, 4, 3, 5 and let + stand for addition. Solve the problem using work optimal
algorithm.(OR) Solve using divide and conquer with n = 8 and p = 8

91. Define the following sequential algorithms, parallel algorithms, speedup, asymptotic
speedup, linear speedup, total work done by algorithm, efficiency of the algorithm, work
optimal.

92. What are the steps involved in solving a problem in parallel. Obtain the maximum speedup
when p = 10 and the various values of f= 0.5, 0.1, 0.01.

93. What are the different ways of resolving read and write conflicts.
94. What do you mean by Prefix computation problem? How do you solve it using Sequential
and parallel methods?

95. Explain the List ranking Problem.

96. What is the procedure to be followed by any parallel computer while performing an
activity?