ADVANCED DATA STRUCTURES & ALGORITHMS- CS610202

UNIT 1: ALGORITHM AND ANALYSIS OF ALGORITHM

PART A(2 MARKS)
Q.NO QUESTION BT LEVEL COMPETENCE
1. Define Algorithm 1 REMEMBER
2. What is Algorithm Design Technique? 1 REMEMBER
3. Differentiate Time and Space Efficiency? 3 APPLYING
4. List the Important Problem types in Data 1 REMEMBER
Structure
5. How will you measure Input Size of Algorithms 2 UNDERSTAND
6. Define Best Case Efficiency? 1 REMEMBER
7. List the Basic Efficiency Classes 2 UNDERSTAND
8. Define Recurrence Relation? 2 UNDERSTAND
9. What is Non Recursion Relation? 2 UNDERSTAND
10. Define Non Recursive Algorithm? 2 UNDERSTAND
11. Define Worst Case Efficiency 2 UNDERSTAND
12. What is Average Case Efficiency 1 REMEMBER
13. Differentiate Best, Worst and Average Case 2 UNDERSTAND
Efficiency
14. Define Asymptotic notation 2 UNDERSTAND
15. Write Importance of Efficient Algorithms 1 REMEMBER
PART B(13 MARKS)
1. Explain Briefly About Algorithm and It’s 1 REMEMBER
Importance
2. Explain About Algorithms as a problem solving 1 REMEMBER
technique
3. Discuss About Time and Space complexity of 2 UNDERSTAND
algorithms
4. Discuss About Asymptotic analysis 2 UNDERSTAND
5. Explain and Differentiate Best, Worst and Average 1 REMEMBER
Case Efficiency
6. Discuss About Asymptotic Notation 2 UNDERSTAND
7. Discuss About The Tree Methods in Data 2 UNDERSTAND
Structures
PART C(15 MARKS)
1. Explain Briefly About Algorithm and It’s 5 EVALUATE
Importance
2. Discuss About The Tree Methods in Data 5 EVALUATE
Structures
 ADVANCED DATA STRUCTURES & ALGORITHMS- CS610202

UNIT 2: HIERARCHICAL DATA STRUCTURES

PART A(2 MARKS)
Q.NO QUESTION BT LEVEL COMPETENCE
1. Define Binary Search Trees 1 REMEMBER
2. Querying a Binary Search Tree 2 UNDERSTAND
3. Define Insertion and Deletion 1 REMEMBER
4. Differentiate Between Insertion and Deletion 3 UNDERSTAND
5. Define Red Black trees 1 REMEMBER
6. What are the Properties of Red-Black Trees 1 REMEMBER
7. Define Rotations 2 UNDERSTAND
8. Define B -trees 2 UNDERSTAND
9. What are the Basic operations on B-Trees 2 UNDERSTAND
10. What Deleting a key from a B-Tree 2 UNDERSTAND
11. Define Heap Implementation 2 UNDERSTAND
12. Define Fibonacci Heaps 1 REMEMBER
13. Write the Structure of Fibonacci Heaps 2 UNDERSTAND
14. Define Decreasing a key 1 REMEMBER
15. Define Deleting a Node 1 REMEMBER
PART B(13 MARKS)
1. Explain in Detail About Binary Search Tree 1 REMEMBER
2. Discuss About Insertion and Deletion 2 UNDERSTAND
3. Discuss About Red Black Trees 2 UNDERSTAND
4. Discuss About B-Tree 2 UNDERSTAND
5. Explain in Detail About Heap Implementation 1 REMEMBER
6. Discuss About Fibonacci Heaps 2 UNDERSTAND
7. Discuss About Bounding the maximum degree. 2 UNDERSTAND
PART C(15 MARKS)
1. Discuss About Fibonacci Heaps 5 EVALUATE
2. Explain in Detail About B-Tree 5 EVALUATE
 ADVANCED DATA STRUCTURES & ALGORITHMS- CS610202

UNIT 3: GRAPHS
PART A(2 MARKS)
Q.NO QUESTION BT LEVEL COMPETENCE
1. Write the concept of Prim’s Spanning Tree. 1 REMEMBER
2. What is the purpose of Dijikstra’s Algorithm? 1 REMEMBER
3. How efficient is Prim’s Algorithm? 2 UNDERSTAND
4. Mention the two classic algorithms for the 1 REMEMBER
Minimum Spanning Tree Problem.
5. What is the Purpose of the Floyd Algorithm? 2 UNDERSTAND
6. What are the Conditions Involved in the Floyd’s 1 REMEMBER
Algorithm
7. Write the concept of Kruskal’s algorithm. 1 REMEMBER
8. Define spanning tree and Minimum Spanning 2 UNDERSTAND
Tree Problem
9. Define the Single Source Shortest Paths Problem. 1 REMEMBER
10. Mention the methods for Generating Transitive 2 UNDERSTAND
Closure of Digraph
11. What do you meant by Graph Traversals? 1 REMEMBER
12. Define Depth First Search DFS 2 UNDERSTAND
13. Write down the steps involved in DFS 1 REMEMBER
14. Define Breadth First Search (BFS) 2 UNDERSTAND
15. Write down the steps involved in Breadth First 2 UNDERSTAND
Search (BFS)
PART B(13 MARKS)
1. Explain in Detail About Breadth-First Search & Depth- 1 REMEMBER
First Search
2. Write a Short Notes in Minimum Spanning Trees 1 REMEMBER
3. Discuss in Detail About Kruskal Algorithm with an 2 UNDERSTAND
Example
4. Discuss in Detail About Prim’s Algorithm with an 2 UNDERSTAND
Example
5. Write About The Bellman-Ford algorithm with an 1 REMEMBER
Example
6. Discuss in Detail About Dijkstra‘s Algorithm 2 UNDERSTAND
7. Discuss in Detail About the Floyd-Warshall 2 UNDERSTAND
 Algorithm
PART C(15 MARKS)
1. Discuss in Detail About Kruskal Algorithm and 5 EVALUATE
Prim’s Algorithm with an Example
2. Discuss in Detail About Dijkstra‘s Algorithm and 5 EVALUATE
Floyd-Warshall Algorithm

ADVANCED DATA STRUCTURES & ALGORITHMS- CS610202

UNIT 4: ALGORITHM DESIGN TECHNIQUES

PART A(2 MARKS)
Q.NO QUESTION BT LEVEL COMPETENCE
1. Define Dynamic Programming 1 REMEMBER
2. What is a Multi-stage graphs 2 UNDERSTAND
3. Define Flow Shop Scheduling 1 REMEMBER
4. Define Greedy Algorithm 1 REMEMBER
5. What is Tree Vertex Splitting 1 REMEMBER
6. Define Job sequencing with deadlines 2 UNDERSTAND
7. What is Back Tracking 2 UNDERSTAND
8. What is difference between Recursion and 2 UNDERSTAND
Backtracking
9. Define Graph Coloring 2 UNDERSTAND
10. What are the Types of Graph Coloring 2 UNDERSTAND
11. Define Knapsack Problem 1 REMEMBER
12. Why is it called Knapsack Problem 2 UNDERSTAND
13. Write the Types of Knapsack Problem 1 REMEMBER
14. What is the complexity of a Multistage Graph? 2 UNDERSTAND
15. What is Permutation Flow Shop Scheduling? 2 UNDERSTAND
PART B(13 MARKS)
1. Explain in Detail About Greedy Algorithm 1 REMEMBER
2. Write a shorts notes on Tree Vertex Splitting 2 UNDERSTAND
3. What is Backtracking? Write a difference between 1 REMEMBER
Recursion and Backtracking
4. Explain in Detail About Graph Coloring 2 UNDERSTAND
5. Write a short notes in Knapsack Problem 1 REMEMBER
6. Explain in Detail About Multi-stage graphs 2 UNDERSTAND
7. Explain in Detail About Tree Vertex Splitting 2 UNDERSTAND
PART C(15 MARKS)
1. Write a short notes in Knapsack Problem 5 EVALUATE
2. Explain in Detail About Greedy Algorithm 5 EVALUATE
 ADVANCED DATA STRUCTURES & ALGORITHMS- CS610202

UNIT 5: NP – Complete and NP - Hard

PART A(2 MARKS)
Q.NO QUESTION BT LEVEL COMPETENCE
1. What does NP stand for in data structure? 1 REMEMBER
2. Write an example of a NP problem? 1 REMEMBER
3. Define P and NP Class? 2 UNDERSTAND
4. What is NP full used for? 2 UNDERSTAND
5. What is NP- Complete Examples? 1 REMEMBER
6. Define Polynomial Time 1 REMEMBER
7. Define Clique Decision Problem 2 UNDERSTAND
8. Define Traveling Salesman Problem 1 REMEMBER
9. What do you mean by clique decision problem 2 UNDERSTAND
10. What is the traveling salesman problem involves? 2 UNDERSTAND
11. What are the advantages of travelling salesman 2 UNDERSTAND
problem
12. What is polynomial time 2 UNDERSTAND
13. What is the importance of polynomial time 2 UNDERSTAND
14. What are the advantages of Clique Decision 2 UNDERSTAND
Problem
15. What is the importance of NP 2 UNDERSTAND
PART B(13 MARKS)
1. Explain in Detail About Polynomial Time and Non 2 UNDERSTAND
Polynomial Time
2. Write shorts notes on Clique Decision Problem 3 APPLY
3. Explain in Detail About Traveling Salesman 1 REMEMBER
Problem
4. What is polynomial time? Write it’s Importance 2 UNDERSTAND
also.
5. Explain in Detail About NP-Completeness 2 UNDERSTAND
6. Write a shorts on Polynomial Time and Non 3 APPLY
Polynomial Time
7. Explain in Detail About Clique Decision Problem 3 APPLY
PART C(15 MARKS)
1. Explain in Detail About Traveling Salesman 5 EVALUATE
Problem and its Advantages
2. Explain in Detail About NP-Completeness 5 EVALUATE