Anna University Chennai B.Sc Computer Science DESIGN OF ALGORITHMS Question paper

[venus]

Anna University Chennai B.Sc Computer Science DESIGN OF ALGORITHMS Question paper

Computer Technology

DESIGN OF ALGORITHMS

(Common to B.Sc. Information Technology)

PART A (10 X 2 = 20 marks)

1. What do you mean by algorithm validation?
2. Compare direct and indirect recursive algorithms.
3. Show the binary decision tree for binary search. (assume no. of elements=14)
4. Write an algorithm for finding maximum and minimum in a straight forward
method.
5. State the principle of optimality.
6. Show the diagrammatic representation of graph with negative cycle.
7. Distinguish between preemptive and non preemptive schedule.
8. Define articulation point. Give example.
9. What is the total number of nodes in 8queens state space tree?
10. What is Branchand Bound method?

PART B (5 X 16 = 80 marks)

11. (i) Find an optimal solution to the knapsack instance n7, m=15 (6)

(p1, p2, p3 to p7) = (10,5,15,7,6,18,3) and
(w1,w2,w3, to w7) = (2,3,5,7,1,4,1)

(ii) Write an algorithm to find the shortest path from one node to every other node
in the graph. Illustrate with an example. (10)

12. (a) (i) What is algorithm? Explain the criteria to be satisfied in every algorithm. (6)

(ii) Devise an recursive algorithm to compute the following binomial coefficient.
Analyse its worstcase and bestcase performance. (10)

n n!
=
m m! (nm)!

(b) (i) How do we analyze the performance of an algorithm? Give an example. (8)

(ii) Explain the various asymptotic notations used in algorithm. (8)





13. (a) (i) Write a recursive binary search algorithm. Analyze its time complexity. (8)

(ii) Sort the following numbers using merge sort. (8)

310,285,179,652,351,423,867,254,450,220

Or
(b) (i) Write an algorithm for Quick sort. Give an example. (10)

(ii) Compare the performance analysis of merge sort and Quick sort. (6)

14. (a) (i) Explain the use of Traveling Salesman problem with an example. (10)

Or
(ii) Write a note on flow shop scheduling (6)

(b) (i) Write an algorithm to count the number of lead nodes in a binary tree?
What is its time complexity? (6)

(ii) Explain Depth First Search algorithm. (8)

(iii) Define spanning tree (2)

15. (a) Discuss the use of backtracking in solving 8queens problem. Analyze its
Performance measures. (16)

or

(b) (i) Write down the control abstraction for LC search (6)

(ii) Explain the method of solving knapsack problem using BranchandBound
Technique.

Can you provide me the syllabus for B.E. Computer Science and Engineering - CS8401- Design & Analysis of Algorithms – of Anna University on which the question paper is based?

[sumit]

The syllabus for B.E. Computer Science and Engineering - CS8401- Design & Analysis of Algorithms – of Anna University is as follows:



DESIGN AND ANALYSIS OF ALGORITHMS 3 0 2 4

OBJECTIVE
Understanding various algorithm design techniques, and to know how to apply those techniques to various problems. Also, gives an understanding of parallel algorithm design, and provides the idea of NP-class of problems and their approximate solutions.


UNIT – I ANALYSIS & DIVIDE-AND-CONQUOR 9
Introduction to Algorithms – Growth of functions – Solving recurrence equations:
Substitution method, Iteration method and Master method – Finding Maximum and Minimum – Selection – Strassen’s Matrix Multiplication – Convex Hull
Lab Component: 6
Implementing some recursive algorithms and study its theoretical time vs empirical time – Implement and analyze selection problem.


UNIT – II GREEDY & DYNAMIC PROGRAMMING 9
Greedy Approach: General Method – Knapsack problem – Minimum cost spanning trees – Single source shortest path problem. Dynamic Programming:
Principle of optimality – All pairs shortest path problem – Longest common subsequence – Traveling salesperson problem
Lab Component: 6
Implement and analyze: Minimum spanning tree problem and Traveling salesperson problem.


UNIT – III BACKTRACKING & BRANCH-AND-BOUND 9
Backtracking: General method – 8 Queens Problem – Graph coloring – Sum of subset problem – Hamiltonian cycle Branch and Bound – Knapsack problem – Traveling salesman problem
Lab Component: 6
Implement and analyze: Sum of subsets – Implement Branch and Bound based traveling salesperson problem and compare with dynamic programming.


UNIT – IV STRING MATCHING & PARALLEL ALGORITHMS 9
Simple string matching – KMP String matching algorithm – Boyer Moore String matching algorithm Parallel algorithms: PRAM models – Prefix computation –
List ranking – Finding the maximum – Odd-Even merge sort – Sorting on a mesh
– Bitonic sort.
Lab Component: 6
Implement and compare simple string matching and KMP algorithms. Implement prefix computation algorithm by using multiple threads or processes.


UNIT – V NP PROBLEMS & APPROXIMATION ALGORITHMS 9
NP-completeness – Polynomial time verification – Theory of reducibility – Circuit satisfiability - NP-completeness proofs – NP-complete problems: Vertex cover, Hamiltonian cycle and Traveling Salesman problems – Approximation Algorithms – Approximation algorithms to vertex-cover and traveling salesman problems.
Lab Component: 6
Implement vertex cover and traveling salesman problems using approximation algorithm.
TOTAL: 45 + 30 = 75


TEXT BOOKS:
1. Ellis Horowitz, Sartaj Sahni and Sanguthevar Rajasekaran, Fundamentals of Computer Algorithms, Second Edition, Universities Press, Hyderabad, 2008.
2. Thomas H Cormen, Charles E Leiserson, Ronald L Rivest and Clifford Stein, Introduction to Algorithms, Second Edition, Prentice Hall of India, New Delhi, 2007


REFERENCES:
1. Kenneth A. Berman and Jerome L. Paul, Algorithms, Cengage learning India Edition, New Delhi, 2002.
2. Sara Baase and Allen Van Gelder, Computer Algorithms – Introduction to Design & Analysis, Third Edition, Pearson Education, New Delhi, 2000.