Powered by ZigaForm version 3.7.8

Enter your keyword

ADVANCED DATA STRUCTURES(18D08102)

UNIT-I

1. What is Computer Algorithms? Briefly Discuss about the Role of Algorithms in Computing.

2. Explain How an Algorithm is a technology and What Kinds of Problems are solved by Algorithm?

3. What are the Characteristics of an algorithm & Briefly Explain Asymptotic notations

4. a. Discuss about Growth of Functions in Asymptotic Notation.

b. Explain Insertion sort Algorithm with examples?

5. How to analyse an Algorithm Explain with Examples

6. Discuss about the Following Methods in Recurrences

a. SUBSTITUTION METHOD b. BY ITERATIVE METHOD

7. Discuss about the Following Methods in Recurrences

a. BY RECURSSION TREE METHOD b. BY MASTER METHOD:

8. Explain about Standard Notations and Common Functions are performed by Algorithms.

9. Create a Template in C++ to perform Insertion and deletion operations in a Doubly Linked list.

10. Define ADT. Explain array ADT. Give a C++ program to construct a stack of integers and to

perform all necessary operations on it.

UNIT-II

1. Define BST? Explain all the operations of binary search tree with help of algorithm?

2. Construct a binary search tree by inserting the keys 4, 12, 8, 16, 6, 18, 24, 2, 14, 3. Draw the tree following each insert. From the tree delete keys 6, 14, 16 and 4. Draw the search tree after each deletion.

3. a. Briefly Discuss about Tree Traversals with Algorithms.

b. Explain the insertion and deletion operations performed on binary heap with an example.

4. a. What is searching? Explain Binary Search technique with example

b. Create a binary tree from the following in-order and pre-order traversal data In-order traversal data:      g,d,h,b,e,i,a,f,j,c.        Pre-order traversal data: a,b,d,g,h,e,i,c,f,j.

5. a. Briefly Discuss about Representation of Binary search tree.

b. What is a binary search tree (BST) and specify the steps showing the construction of a BST for the following data       10, 08, 15, 12, 13, 07, 09, 17, 20, 18, 04, 05

6. a. What is a Red-black tree? Explain the Rotations of Red-black trees.

b. Start with an empty red black tree and insert the following keys in the given order: 20, 10, 5, 30, 40, 57, 3, 2, 4, 35, 25,  18, 22, 21. Draw the figures depicting your tree immediately after insertion and following the rebalancing rotation or color change. Label all nodes with their color and identify the rotation type.

7. Describe the following binary tree’s with an example (i). Full binary tree (ii). Complete binary tree (iii) left & right skewed binary tree

8. a. What is a B-Tree. Specify its properties and describe the construction of a B-Tree for the following elements 5, 2, 13, 3, 45, 72, 4, 6, 9, 22

b. How do you compute the height of B Tree? Explain.

9. a. Elaborate the significance of Red-Black tree.

b. Explain the Basic operations of B tree.

10. a. Briefly Discuss about Bounding the maximum degree.

      b. Write a program for binary search tree ADT.

11. a. Define B-Tree? Generate a B-Tree of order 3 (2-3 tree) for the following key values 25,10,12,15,39,64,53

      b. Explain the Binary Trees and their representation with an example.

12. a What is binary tree? What for it is used? Mention its properties.

     b. Explain about Binary search trees with an example.

UNIT-III

1. a. Discuss about Representations of graphs.

    b. Define Minimum Spanning Trees and Explain with Examples.

2. What is Traversal? Briefly Explain wit suitable Example.

3. Define DFS? Explain with an Algorithm.

4. Explain about different graph storage representations with examples.

5. Explain the finding shortest path algorithms with Examples.

6. a. What are the properties of BFS&DFS.

b. Write the pseudo code for Depth First Traversal Technique.

7. What is Traversal? Explain about DFS Traversal and its algorithm with an example.

8. Where to use DFS and Explain the Topological sort algorithms with examples.

9. Briefly Explain the Strongly connected components.

10. Explain the Kruskal’s algorithm with Example.

11. Explain the Prim’s algorithm with Example.

12. Explain Finding the Single-Source Shortest Paths using Bellman-Ford algorithm.

13. a. Explain Finding the Single-Source Shortest Paths using Dijkstra‘s Algorithm .

      b. Explain All-pairs shortest paths with Examples.

14 .a. Explain Matrix Multiplication with Examples.

      b.The Floyd-Warshall Algorithm.

15. Briefly Discuss about Travelling Sales person problem with Algorithm.

UNIT-IV

1. Explain the Elements of Dynamic Programming.

2. Discuss about Matrix-Chain Multiplication.

3. Explain Characterizing a longest common subsequence.

4. Discuss about Longest common subsequence.

5. Briefly Discuss about An activity-selection problem in Greedy Algorithms.

6. Explain Greedy versus dynamic programming.

7. Explain Huffman codes & Prefix codes.

8. Explain Greedy Algorithms With examples.

9. Discuss about Constructing a Huffman code.

10. Briefly Explain Elements of the greedy strategy in Greedy Algorithms.

UNIT-V

1. What are the Differences between NP,NP-Complete and NP-Hard?

2. Define NP-Completeness? Explain Reducability with Examples.

3. What are the NP-Hard Problems? Explain any one (TSP) with Examples.

4. Describe NP-Complete problems with Examples.

5. Briefly Explain the Following

a. P & NP-Complete        b. NP&NP-Hard

6. Discuss the NP-Complete with Algorithm and Examples.

7. Define P, NP and NP-Complete problems. Give an Example for each.

8. Define PSPACE and NPSPACE.What can you say about the Relationship between PSPACE and NPSPACE ?

9. Discuss about the Polynomial-Time Verification with Examples.

10. Briefly Explain NP-Completeness with Proofs and examples.