# Dr. A.P.J. Abdul Kalam University BE IV SEM (CS) ANALYSIS & DESIGN OF ALGORITHM [CS228T] June 2021 Question Paper

Dr. A.P.J. Abdul Kalam University

Bachelor of Engineering

Fourth Semester Main Examination, June-2021

ANALYSIS & DESIGN OF ALGORITHM [CS228T]

Branch : CSE

Time: 3:00 Hrs Max Marks 70

Note: - Attempt any five questions out of eight.

All Questions carry equal marks.

Q.1 (a) What is an Algorithm? What are Parallel Algorithms?

(b) Define Spanning tree. Discuss design steps in Prim’s algorithm to

construct minimum spanning tree with an example.

Q.2 (a) Explain divide and conquer algorithms? Explain Kruskal’s algorithm.

(b) Explain the various asymptotic notations used in algorithm design?

Q.3 (a) Explain Warshall’s & Floyd’s Algorithm.

(b) Explain the concept of Dynamic Programming?

Q.4 (a) What is Knapsack problem in greedy strategy?

(b) Define optimal binary search trees with example.

Q.5 (a) Discuss the solution for Travelling salesman problem using branch &

bound technique.

b) Define Hamiltonian cycle with example?

Q.6 (a) Explain the 8-Queen’s problem & discuss the possible solutions.

(b) Define Branch and Bound method?

Q.7 (a) Explain Graph coloring with example.

(b) Define height balanced tree? Explain all the rotation perform to

balance the tree with example?

Q.8 (a) Give a suitable example & explain the Breadth first search & Depth

first search.

(b) Explain about Knapsack Problem using back tracking with example?

Scanned Copies:

Share This
Previous Post
Next Post

#### Shiva

B.E Civil Engineer Graduated from Government College of Engineering Tirunelveli in the year 2016. She has developed this website for the welfare of students community not only for students under Anna University Chennai, but for all universities located in India. That's why her website is named as www.IndianUniversityQuestionPapers.com . If you don't find any study materials that you are looking for, you may intimate her through contact page of this website to know her so that it will be useful for providing them as early as possible. You can also share your own study materials and it can be published in this website after verification and reviewing. Thank you!

#### 0 comments:

Pen down your valuable important comments below