DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING ALGORITHM ANALYSIS
UNIT –I ALGORITHM ANALYSIS
PARTA
1. What is an Algorithm? May/June 2006, Nov/Dec 2008
2. State the Euclid’s algorithm for finding GCD of two given numbers.
3. What are Sequential Algorithms?
4. What are Parallel Algorithms?
5. What is Exact and Approximation algorithm?
6. What is Algorithm Design Technique? Nov/Dec 2005
7. Define Flowchart.
8. Explain Algorithm’s Correctness
9. What is Efficiency of algorithm?
10. What is generality of an algorithm?
11. What is algorithm’s Optimality?
12. What do you mean by ″″″Sorting” problem?
13. What do you mean by ″″″Searching” problem?
14. What do you mean by ″″″Worst caseEfficiency” of an algorithm?
15. What do you mean by ″″″Best caseEfficiency” of an algorithm?
16. Define the ″″″Averagecase efficiency” of an algorithm?
17. What do you mean by “Amortized efficiency”?
18. How to measure the algorithm’s efficiency?
19. What is called the basic operation of an algorithm?
How to measure an algorithm’s running time?
20. Define order of growth.
21. Define Big oh notation May/June 2006, April/May 2008
22. Prove that 100n+5 ∈ O (n2
)?
23. Define Ω notation
24. Prove that n3
∈Ω(n2
)?
25. Define Θ  notation
26. Prove that( ½)n(n1) ∈ Θ(n2
)
27. What is the use of Asymptotic Notations?
PARTB
1. (a). Define the asymptotic notations used for best case average case and worst case analysis
of algorithm. (8)
(b)Write an algorithm for finding maximum element of an array; perform best and average
case complexity with appropriate order notations. (8)
2. Write an algorithm to find mean and variance of an array perform best, worst and
average case complexity, defining the notations used for each type of analysis. (16)
3. Derive the recurrence relation for Fibonacci series, perform complexity analysis for the
same.(16)
4. Explain the various asymptotic notations with the properties.(16)
5. Explain linear search with example.(16)
UNIT II  DIVIDE AND CONQUER
PARTA
1) Explain divide and conquer algorithms
2) Define Merge Sort
3) Define Binary Search
4) What can we say about the average case efficiency of binary search?
5) Define Binary Tree
6) How divide and conquer technique can be applied to binary trees?
7) Explain Internal and External Nodes
8) Define Preorder, inorder and postorder Traversal
9) Define the Internal Path Length
10) Define the External Path Length
11) Explain about greedy technique
12) Define Spanning Tree
13) Define Minimum Spanning Tree
14) Define minheap
15) Define Kruskal's Algorithm
16) Define Prim's Algorithm
17) Explain Dijkstra's Algorithm
PARTB
1)Explain Knapsack Problem.(16).
2)Explain the algorithm for maximum and minimum numbers in an array.
(16)
3)(a) Give a detailed note on Divide and Conquer techniques.(6)
(b). Sort the following set of elements using merge sort (10)
12,24,8,71,4,23,6,89,56
4)Write An algorithm for searching an element using Binary search method. Give an
example.(16)
5)(a) write a pseudo code for a divide and conquer algorithm for merging two sorted arrays
into a single sorted one. Explain with an example.(12)
(b) Setup an solve a recurrence relation for the number of key
comparisons made by the above pseudo code.(4)
6) (a) Write an algorithm to sort a set of N numbers using insertion sort.(8)
(b) Trace the algorithm for the following set of numbers.
20,35,18,8,14,41,3,39
7)Explain in detail merge sort. Illustrate the algorithm with a numeric
example. Provide complete analysis of the same. (16)
UNIT III  DYNAMIC PROGRAMMING
PARTA
1)Define Dynamic Programming
2) Define Binomial Coefficient
3) Define Transitive closure
4) Explain Warshalls algorithm
4) Explain Allpair shortestpaths problem
5) Explain Floyd's algorithm
6) What does Floyd’s algorithm do?
7) Explain principle of Optimality
8) Explain Optimal Binary Search Trees
9) Explain Knapsack problem
10) Explain the Memory Function technique
11) Explain ″″″Traveling salesman problem”?
PARTB
1)Solve the allpairs shorest path problem for the digraph with the weight matrix given
below.(16)
A B C D
A 0 ∞ ∞ 3
B 2 0 ∞ ∞
C ∞ 7 0 1
D 6 ∞ ∞ 0
2)How will you construct a optimal search tree with example. (16)
3)Explain the Multistage graph with example.(16)
4)Explain the 0/1 knapsack with an algorithm.(16)
5)Describe the Traveling salesman problem & discuss how to solve it using Dynamic
Programming. (16)
UNIT IV  BACKTRACKING
PARTA
l) Explain Backtracking
2) Explain State Space Tree
3) Explain promising and non promising node
4) Explain nQueens problem
5) Explain SubsetSum Problem
6) Explain Branch and Bound Technique
7) Define Feasible Solution
8) Define Optimal solution
9)Mention two reasons to terminate a search path at the current node in a statespace tree of
a branch and bound algorithm.
10) Explain ″″″Graph coloring” problem.
11) Explain Knapsack Problem
PARTB
1. What is Backtracking? Explain in detail.(16)
2. Explain Subsetsum Problem & Discuss the possible solution strategies using
backtracking. (16)
3. Discuss the use of greedy method in solving knapsack problem and subset sum problem.
(16)
4. Write short notes on
(a) Graph coloring (8)
(b) 8Queens problem (8)
5.Apply Backtracking technique to solve the following instance of the subset sum
problems.s=(1,3,4,5) & d=11 (16)
6. Explain subsetsum problem and discuss the possible solution strategies using
backtracking. (16)
7. Explain 8Queens problem with an algorithm. Explain why backtracking is defined as a
default procedure of last resort for solving problems. (10+6)
8. Using Backtracking enumerate how can you solve the following problems
(a) 8queens problem (8)
(b) Hamiltonian circuit problem (8)
UNITV TRAVERSALS, BRANCH AND BOUND
PARTA
1) Define tractable and intractable problems
2) Explain the theory of computational complexity
3)Explain class P problems
4)Explain undecidable problems
5) Explain the halting problem
6) Explain class NP problems
7)Explain NPcomplete problems
8)When a decision problem is said to be polynomially reducible
9) Define a Heuristic
10) Explain NPHard problems
11)Define Traversals.
12)List out the techniques for traversals in graph.
13)What is articulation point.
PARTB
1)Define spanning tree? Discuss the design steps in prims algorithm to construct minimum
spanning tree with example.(16)
2)Explain the method of binding the minimum spanning tree for a connected graph using
prims algorithm.(16)
3)Define spanning tree? Discuss the design steps in kruskal algorithm to construct minimum
spanning tree with example. (16)
4)Compare and contrast the depth first search and birth first search. How do they fit in to
the decrease and conquer strategies.(16)
5)Explain NPhard and NP complete problems with example(16)
6)Explain connected components and biconnected components with pseudocode(16)
7)Give a suitable example and explain the birth first search and depth first search algorithm.
(16)
8)What is branch and bound? Explain detail. (16)
9)Discuss the solution for knapsack problem using branch bound techniques.(16)
