Dr.A.P.J.Abdul Kalam University BE LATERAL III SEM ALL BRANCH Analysis and Design of Algorithms [IT-221] Dec - 2020 Question Paper

Dr.A.P.J.Abdul Kalam University

Bachelor of Engineering

Third Semester Main Examination, Dec-2020

Analysis and Design of Algorithms [IT-221]

Branch: IT

Time: 3:00 Hrs Max Marks 70

Note : 1. Attempt any five questions out of Eight.

           2. All question carry equal marks.

Q.1 a) Define space complexity and time complexity.

(b) How can we prove that Strassen’s matrix multiplications advantageous

over ordinary matrix multiplications?

Q.2 (a) What is minimum spanning trees? Explain in detail.

(b) What is Reliability design using dynamic programming? Explain with

example.

Q.3 (a) Show that Hamiltonian cycle in NP complete.

(b) Differentiate between NP-Complete and NP hard problems.

Q.4 (a) What are “Queues”? Explain how to insert and delete an element from

queue with suitable algorithm

(b) Explain multistage graphs with examples. Write multistage graph

algorithm to forward approach

Q.5 (a) Explain 4-queen problem. Apply backtracking to find the solution.

(b) What do you understand by Graph Traversal? Show how it is done using

the example of BFS by considering the directed graph

Q.6 (a) What are “Queues”? Explain how to insert and delete an element from

queue with suitable algorithm.

(b) Create a B-tree for the following list of elements L = {86, 50, 40, 3, 94,

10, 70, 90, 110, 113, 116} given minimization factor = 3, minimum degree =

2 and maximum degree = 5.

Q.7 (a) What is Reliability design using dynamic programming? Explain with

example.

(b) Solve the subset sum problem using Back tracking where n = 4, m = 18,

w[4] = {5, 10, 8, 13}.

Q.8 Write short notes on:

(i) Least cost search (ii) Asymptotic notation

(iii) Huffman coding (iv) Binary search

Attachment & Scanned Copies:

Share This