`

MOTHER THERESA INSTITUTE OF ENGINEERING AND

TECHNOLOGY
MELUMOI, PALAMANER– 517 408

COURSE FILE
For
ADVANCED DATA STRUCTURES & ALGORITHMS / 20A05301T
(AY 2022-23 II B.TECH CSE I Semester)

Prepared by
G.JAYAGOPI
Associate Professor

Department of
-COMPUTER SCIENCE AND ENGINEERING
`

INDEX

PART I

1. Syllabus
2. Course Information Sheet
3. Course Objectives, Course outcomes
4. Mapping onto PEO & PO
5. Lesson Plan
6. Lecture Notes
7. University Question Paper
8. Internal Question Paper’s With Key
9. Assignment Topics
10. Tutorial Sheets
11. Unit wise Question Bank
12. Gaps & Plans for Add-On Programs
13. Topic beyond the syllabus - References
14. Web References
15. Teacher Log Book/ Attendance Register
`

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY ANANTAPUR

B.Tech (IT)— II-I Sem L T P C

3 0 0 3
(20A0530IT) ADVANCED DATA STRUCTURES AND ALGORITHMS

Course Objectives:
 Learn asymptotic notations, and analyze the performance of different algorithms.
 Understand and implement various data structures.
 Learn and implement greedy, divide and conquer, dynamic programming and backtracking algorithms using
relevant data structures.
 Understand non-deterministic algorithm, polynomial and non-polynomial problems.

Course Outcomes:
 Analyze the complexity of algorithms and apply asymptotic notations.
 Apply non-linear data structures and their operations.
 Understand and apply greedy, divide and conquer algorithms.
 Develop dynamic programming algorithms for various real-time applications.
 Illustrate Backtracking algorithms for various applications.

UNIT – I INTRODUCTION TO ALGORITHMS

Algorithms, Pseudocode for expressing algorithms, Performance Analysis-Space complexity, Time
complexity, Asymptotic Notation- Big oh, Omega, Theta notation and Little oh notation, Polynomial Vs
Exponential Algorithms, Average, Best and Worst Case Complexities, Analyzing Recursive Programs.
UNIT – II TREES PART-I
Trees Part-I
Binary Search Trees: Definition and Operations, AVL Trees: Definition and Operations, Applications.
B Trees: Definition and Operations.
UNIT – III TREES PART-II
Trees Part-II
Red-Black Trees, Splay Trees, Applications.
Hash Tables: Introduction, Hash Structure, Hash functions, Linear Open Addressing, Chaining
Applications.

UNIT – IV DIVIDE AND CONQUER, GREEDY METHOD

Divide and conquer: General method, applications-Binary search, Finding Maximum and minimum,
Quick sort, Merge sort, Strassen’s matrix multiplication.
Greedy method: General method, applications- Job sequencing with deadlines, knapsack problem,
Minimum cost spanning trees, Single source shortest path problem.
`

UNIT – V DYNAMIC PROGRAMMING & BACKTRACKING

Dynamic Programming: General method, applications- 0/1 knapsack problem, All pairs shortest path
problem, Travelling salesperson problem, Reliability design.
Backtracking: General method, applications-n-queen problem, sum of subsets problem, graph coloring,
Hamiltonian cycles.
Introduction to NP-Hard and NP-Complete problems: Basic Concepts.
TEXTBOOKS:
1. Data Structures and algorithms: Concepts, Techniques and Applications, G A V Pai.
2. Fundamentals of Computer Algorithms, Ellis Horowitz, Sartaj Sahni and Rajasekharam, Galgotia
publications Pvt. Ltd.
REFERENCE BOOKS:
1. Classic Data Structures by D. Samanta, 2005, PHI
2. Design and Analysis of Computer Algorithms by Aho, Hopcraft, Ullman 1998, PEA.
3. Introduction to the Design and Analysis of Algorithms by Goodman, Hedetniemi, TMG.

ONLINE LEARNING RESOURCES:

https://www.tutorialspoint.com/advanced_data_structures/index.asp
http://peterindia.net/Algorithms.html
`

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING

COURSE PLAN –ADVANCED DATA STRUCTURES & ALGORITHMS (AY 2022-23)
Faculty Name : G.JAYAGOPI Course: B.Tech
Subject Name with code: Advanced Data
Semester/ Branch : IIYear – I Sem. / CSE
Structures & Algorithms
(20A05301T)
COURSE OBJECTIVE:
The student has to acquire knowledge about:
• Learn asymptotic notations, and analyze the performance of different algorithms.
• Understand and implement various data structures.
• Learn and implement greedy, divide and conquer, dynamic programming and backtracking algorithms
using relevant data structures.
• Understand non-deterministic algorithm, polynomial and non-polynomial problems.
LEARNING OUTCOME:
Understand the concept of python .
 Implement the concepts of packages.
 \Use of API and implement the functions
 To design different applets.
COURSE OUTCOMES:

After completion of the course, students will be able to

 Analyze the complexity of algorithms and apply asymptotic notations.
 Apply non-linear data structures and their operations.
 Understand and apply greedy, divide and conquer algorithms.
 Develop dynamic programming algorithms for various real-time applications.
 Illustrate Backtracking algorithms for various applications.
PO Mapping with Course Outcomes:
CO1- 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12
CO2- 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12
CO3 – 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
CO4 – 1, 2, 3, 4, 5, 6, 8, 11, 12
CO5 – 1, 2, 3, 5, 6, 7, 8, 9, 11
CO6 – 1, 2, 3, 4, 6, 7, 9, 10

TEXTBOOKS:
`

1. Data Structures and algorithms: Concepts, Techniques and Applications, G A V Pai.

2. Fundamentals of Computer Algorithms, Ellis Horowitz, Sartaj Sahni and Rajasekharam, Galgotia
publications Pvt. Ltd.
REFERENCE BOOKS:
1. Classic Data Structures by D. Samanta, 2005, PHI
2. Design and Analysis of Computer Algorithms by Aho, Hopcraft, Ullman 1998, PEA.
3. Introduction to the Design and Analysis of Algorithms by Goodman, Hedetniemi, TMG.

ONLINE LEARNING RESOURCES:

https://www.tutorialspoint.com/advanced_data_structures/index.asp
http://peterindia.net/Algorithms.html
Assignments: 02
S.N Assignment Topic Date of Submission No. of Students Allotted
o Submitted Marks
1 BINARY SEARCH TREES 09.11.2022 65 5
2 DYNAMIC PROGRAMMING 04.12.2022 65 5

Missing Topics Teaching Methodology Mapping to PO

Class Lecture PO1,PO2,PO3,PO4
ADVERSARIAL SEARCH
EXPERT SYSTEMS Class Lecture PO1,PO2,PO3,PO4

Topics Beyond the Syllabus Teaching Methodology Mapping to PO

KNOWLEDGE REPRESENTATION PPT PO1,PO2,PO3,PO4

Seminar Topics:
1. REASONING SYSTEMS FOR CATEGORIES
2. TRUST AND REPUTATION IN MULTI-AGENT SYSTEMS

Course Assessment:
1. 30 Marks for Internal + 70 Marks for University Examination.

2. Student feedback on the course (Scale of 1-5).

3. Mentee for 15 students

HOD
`

Mapping onto PEO & PO

PO Description CO1 CO2 CO3 CO4 CO5
PO: 1 An ability to apply knowledge of YES YES YES YES YES
mathematics, science and engineering.
PO: 2 An ability to design and conduct YES YES YES YES YES
experiments, as well as to analyze and
interpret data.
PO: 3 An ability to design a system, component or YES YES YES YES YES
process to meet desired needs.
PO: 4 An ability to function on multi- disciplinary YES YES YES YES
teams.
PO: 5 An ability to identify, formulate and solve YES YES YES YES
engineering problems.
PO: 6 An understanding of professional and YES YES
ethical responsibility.
PO: 7 An ability to communicate effectively.
PO: 8 The broad education necessary to YES YES YES YES YES
understand the impact of engineering
solutions in a global and societal context.
PO: 9 Recognition of the need for, and an ability YES YES YES YES
to engage in life-long learning.
PO: 10 Knowledge of contemporary issues. YES
PO: 11 An ability to use the techniques, skills, and YES YES YES YES YES
modern engineering tools necessary for
engineering practice.
`

MOTHER THERESA INSTITUTE OF ENGINEERING & TECHNOLOGY

MELUMOI, PALAMANER-517408
Approved By AICTE, New Delhi & Affiliated To JNTUA, Anantapuramu-515002
NAAC Accredited and an ISO 9001:2015 Certified Institution
Department of Computer Science & Engineering

LESSON PLAN

Name of the Faculty : G. JAYAGOPI Academic Year: 2022-2023

Subject Name : ADVANCED DATA STRUCTURES&ALGORITHMS Class: II - CSE
Total Delivery
S. No of
Topic to be covered Reference Book No.of Method
No. Periods
Periods
UNIT-I Introduction to Algorithms Black
1 Algorithms, Pseudocode for expressing T1(1 - 5) 1 1 Board
algorithms
1 Black
2 Performance Analysis T1(6 – 15) 2
Board
T1(16 – 27) 1 Black
3 Space complexity, 3
Board
T1(28 – 29) 1 Black
4 Time complexity 4
Board
Asymptotic Notation – Big oh, Omega, Theta T1(34 – 35) Black
5 2 6
notation and Little oh notation, Board
T1(36 – 39) Black
6 Polynomial Vs Exponential Algorithms 1 7
Board
T1 (40– 45) Black
7 Best and Worst Case Complexities 1 8
Board
8 Analyzing Recursive Programs T1(46 – 58) 2 10 PPT
UNIT-II Trees Part - I: T1(64 – 68) Black
9 1 1
Introduction Board
T1(69 – 80) 2 Black
10 Binary Search Trees: 3
Board
T1(81 – 91) 2 Black
11 Definition and Operations 5
Board
T1(92 – 102) Black
12 AVL Trees: 2 7
Board
T1(103 – 107) Black
13 Definition and Operations 2 9
Board
T1(121 – 129) Black
14 Applications 1 10
Board
T1(130– 133) Black
15 B Trees 1 11
Board
T1(134 – 138) Black
16 Definition and Operations 2 13
Board
UNIT III Trees Part - II: T1(139 – 147) Black
17 1 1
Introduction Board
T1(148 – 153) Black
18 Red – Black Trees, 1 2
Board
19 Definition and Operations, Properties T1(846 – 847) 1 3 Black
`

Board
T1(848 – 854) Black
20 Problems 2 5
Board
21 Splay - Trees T1(855 – 860) 1 6 PPT
22 Definition and Operations, Properties, Types T1(861 – 863) 1 7 PPT
T1(864 – 867) Black
23 Problems, Applications 2 9
Board
T1(876 – 880) Black
24 Hash Tables, Introduction 2 11
Board
T1(881 – 882) Black
25 Hash Structure, Hash Functions 2 13
Board
T1(883 – 888) Black
26 Linear Open Addressing 1 14
Board
T1(889 – 898) Black
27 Chaining and Applications 1 15
Board
UNIT IV Divide and Conquer, Greedy T1(904 – 907) Black
28 Method: 1 1 Board
General method, applications
T1(908 – 912) Black
29 Binary Search, 1 2
Board
T1(913 – 922) Black
30 Finding Maximum and Minimum 1 3
Board
T1(923 – 928) Black
31 Quick sort 1 4
Board
T1(945 – 957) Black
32 Merge sort 1 5
Board
T1(958 – 961) Black
33 Strassen’s matrix multiplication. 1 6
Board
34 Greedy method: General method, applications T1(962 – 972) 1 7 PPT
35 Job sequencing with deadlines T1(973 – 975) 1 8 PPT
36 Knapsack problem, T1(976 – 980) 1 9 PPT
37 Minimum cost spanning trees T1(986 – 987) 1 10 PPT
38 Single source shortest path problem T1(988 – 991) 1 11 PPT
UNIT V Dynamic Programming & T1(1001 – 1017) Black
39 Backtracking: 1 1 Board
General method, applications
T1(1018 – 1020) Black
40 0/1 Knapsack problem 1 2
Board
T1(1021 – 1034) Black
41 All pairs shortest path problem 1 3
Board
T1(1035 – 1040) Black
42 Travelling salesperson problem 1 4
Board
T1(1041 – 1048) Black
43 Reliability design 1 5
Board
T1(1049 – 1055) Black
44 Backtracking: General method, applications 1 6
Board
45 n-queen problem T1(1059 – 1061) 1 7 PPT
46 Sum of subsets problem T1(1062 – 1063) 1 8 Black
`

Board
47 Graph coloring, Hamiltonian cycles. T1(1064 – 1065) 1 9 PPT
Introduction to NP-Hard and NP-Complete T1(1066 – 1068) Black
48 1 10
problems: Basic Concepts. Board

TEXTBOOKS:
1. Data Structures and algorithms: Concepts, Techniques and Applications, G A V Pai.
2. Fundamentals of Computer Algorithms, Ellis Horowitz, Sartaj Sahni and Rajasekharam, Galgotia
publications Pvt. Ltd.
REFERENCE BOOKS:
1. Classic Data Structures by D. Samanta, 2005, PHI
2. Design and Analysis of Computer Algorithms by Aho, Hopcraft, Ullman 1998, PEA.
3. Introduction to the Design and Analysis of Algorithms by Goodman, Hedetniemi, TMG.

Signature of Faculty HOD

`

QUESTION BANK
SUBJECT : Advanced Data Structures & Algorithms YEAR / SEM: II Year / I Sem

UNIT I
PART-A
Q.No Questions BT Competence
Level
1 Express the term data structures. BTL 2 Understand

2 Identify the types of data structures. BTL 4 Analyze

3 List the advantages of data structures. BTL 1 Remember

4 Tabulate the difference between stack and queue. BTL 1 Remember

5 Distinguish graph and tree. BTL 2 Understand

6 Interpret the various applications of stack. BTL 2 Understand

7 Differentiate Recursion from normal function. BTL 4 Analyze

8 Give the various sorting techniques. BTL 2 Understand

9 What is meant by Recursion? BTL 1 Remember

10 Apply any of the implementation strategy of stack. BTL 3 Apply

11 Compose on the term set representation. BTL 6 Create

12 Measure O (n log n) comparison strategy. BTL 5 Evaluate

13 Formulate the equation to calculate running time of a program. BTL 6 Create

14 State the various set representations. BTL 1 Remember

15 Show the narration of dynamic programing. BTL 3 Apply

16 Define graph. BTL 1 Remember

17 Name the different types sorting techniques. BTL 1 Remember

18 Compare heap sort and merge sort. BTL 4 Analyze

`

19 Illustrate on comparison sort. BTL 3 Apply

20 Evaluate an algorithm to perform any of the traversal. BTL 5 Evaluate

PART B
1 i).Summarize on different types of data structures BTL 5 Evaluate
ii). Explain the various ADTs.
2 List the various set representations in data structures. BTL 1 Remember

3 i).Define deterministic data structures. BTL 1 Remember

ii).Describe ADT elaborate stack using it.

4. i). Identify the various operations in set representation. BTL 1 Remember

ii). Examine the applications of stack.

5 i).Discuss the Queue ADT. BTL 2 Understand

ii). Explain the concept of Recursion

6 Differentiate the various operations in stack and Queue BTL 4 Analyze

7 Implement Tree traversal using an algorithm. BTL 3 Apply

8 Recall the different types of trees along with example. BTL 2 Understand

9 i).Formulate the Graph Traversal Techniques. BTL 6 Create

ii).Compose any application of graph.

10 Implement the Divide and Conquer strategy using an BTL 3 Apply

algorithm.

11 Find the various sorting techniques write an elaboration for BTL 1 Remember
Radix sort

12 Compare and Contrast Heap sort and Quick sort BTL 4 Analyze

13 Analyze theO(n log n) for any of the sorting techniques. BTL 4 Analyze

14 With suitable examples, Summarize on time sort on a quick BTL 2 Understand

sort.

UNIT II
PART-A
Q.No Questions BT Competence
Level
1 Apply the hashing technique to implement. BTL Apply
3
2 Analyze the fundamental operations of set. BTL Analyze
4
3 Construct the Binary Tree. BTL Apply
`

3
4 List the features of Binary search Tree. BTL Remember
1
5 What is optimal binary search? BTL Remember
1
6 Compare and Contrast Binary Tree and Binary search Tree. BTL Understand
2
7 Illustrate a simple disjoint-set union algorithm. BTL Apply
3
8 Perform traversal in Binary tree BTL Analyze
4
9 Contrast heaps and queues with examples. BTL Understand
2
10 Develop set union algorithm. BTL Create
6
11 Name the dictionaries. BTL Remember
1
12 Formulate the steps of merge able heaps. BTL Create
6
13 Evaluate priority Queues. BTL Evaluate
5
14 Define concatenable queues. BTL 1 Remember

15 Express the term partitioning. BTL Understand

2

16 State UNION-FIND problem. BTL Remember

1
17 Interpret merge able heaps and concatenable queues. BTL Understand
2
18 Analyze on priority Queues. BTL Analyze
4
19 Label the algorithm for disjoint-set. BTL Remember
1
20 Create a binary search tree. BTL 5 Evaluate

PART-B
1 i).Discuss fundamental operations of sets. BTL Understand
ii).Express an example for the operations on set. 2

2 Illustrate Hashing technique? Give algorithm and example. BTL Apply

3

3 Describe about basic concepts of Binary Tree BTL Remember

1
4 Develop algorithm to implement Binary Search Tree BTL Create
6
5 i) .State the optimal binary search tree. BTL Remember
ii).Develop an algorithm for the same. 1
`

6 i).Express the features of Binary Search Tree. BTL Understand

ii).Differentiate Binary Tree and Binary Search Tree 2

7 Point out the steps in disjoint-set union algorithm. BTL Analyze

4
8 i).Examine tree structure for UNION -FIND problem BTL Remember
ii).Give an example for the same. 1
9 Tabulate various balanced Tree schemes. BTL Remember
1
10 i).Design an algorithm for balanced tree schemes BTL Understand
ii).Discuss on priority queues. 2

11 i).Explain the algorithm for priority queues. BTL Evaluate

ii).Explain about Merge able heaps 5

12 Analyze on the following. BTL Analyze

i). Concatenable queues 4
ii).Partitioning.

13 Arrange the following G,P,K,L,A,B,M,O,Z,C using. BTL Analyze

i). Binary Tree. 4
ii).Binary Search Tree.

14 Construct a tree structure for UNION-FIND problem. BTL Apply

3
UNIT III
PART-A
Q.No Questions BT Competence
Level
1 Express the term dynamic programming BTL Understand
2
2 Define backtracking. BTL Understand
2
3 Recall the algorithm for divide and conquer. BTL Remember
1
4 List the problem of multiplying long integers. BTL Remember
1
5 Distinguish long integers and short integers. BTL Understand
2
6 Distinguish dynamic programing from others. BTL 2 Understand

7 Name the techniques for balancing sub problems. BTL Remember

1
8 Evaluate triangulation problem. BTL Evaluate
5
9 State the triangulation problems. BTL Remember
1
10 Design the triangulation problem. BTL Create
6
`

11 Classify the Greedy algorithms. BTL Analyze

4
12 Illustrate Backtrack search. BTL Apply
3
13 Assess the methods to implement backtrack search. BTL 5 Evaluate

14 Tabulate the parallel algorithms. BTL Remember

1

15 Show the advantages of branch and bound strategy. BTL Apply

3
16 Point out the local search algorithms BTL Analyze
4
17 What is randomized algorithm? BTL Remember
1
18 Illustrate the approximation algorithm. BTL Apply
3
19 Classify the types of local search algorithms. BTL 4 Analyze

20 Generalize the string algorithms. BTL6 Create

PART-B
1 Discuss the Divide and Conquer algorithms. BTL Understand
2
2 State the problems of multiplying long integers. BTL Remember
1

3 i).List the steps for Balancing of sub problems. BTL Remember

ii).Describe the divide and conquer algorithm. 1

4 Design and develop the Triangulation problem with an BTL Create

algorithm. 6

5 i).What is Greedy Technique? BTL Remember

ii).Design and implement an algorithm for Greedy method. 1

6 Summarize on Backtracking along with an example. BTL Understand

2
7 i).Differentiate backtrack search from the other searching BTL Analyze
4
methods.
ii).Select the example to narrate the backtrack search.
8 Recommend the techniques BTL Evaluate
i).Dynamic programming 5
ii).Balancing the sub problems.

9 Examine the Branch and Bound technologies with an BTL Apply

example. 3

10 i).Analyze the Local search algorithms. BTL Analyze

ii).Demonstrate string algorithm along with an example. 4
`

11 Express the local search algorithm along with an example. BTL Understand
2
12 i).Explain the String algorithm. BTL Analyze
ii).Point out the advantages of parallel algorithm. 4

13 Tabulate the difference between local search algorithms BTL Remember

14 Show the advantages of Randomized algorithm along with the BTL Apply
apllications 3

UNIT IV
PART-A
Q.No Questions BT Competence
Level
1 Describe Binary search Tree. BTL Understand
2
2 Illustrate on insertion and deletion of Red Black Tree. BTL Apply
3
3 List the properties of Red Black Tree. BTL Remember
1
4 Analyze the term rotation. BTL Analyze
4
5 Quote the importance of Red Black Tree. BTL Remember
1
6 Define B Tree BTL Remember
1
7 Express the insertion operation in B Tree BTL Understand
2
8 State deletion key in B Tree. BTL Remember
1
9 Differentiate Binary search tree and B Tree. BTL 2 Understand

10 Show the operations of B Tree. BTL Apply

3
11 Compare Red Black tree and B Tree. BTL Evaluate
5
12 Define Fibonacci Heap. BTL Remember
1

13 Integrate the deletion operation of the B Tree. BTL 6 Create

14 Discriminate Binary Search Tree and Red Black tree. BTL Evaluate
5
15 Quote rotation process in trees. BTL Remember
1
16 Express the deletion mechanism of binary search tree. BTL Understand
2
17 Formulate the operation of merge able heaps. BTL 6 Create

18 Categorize the process of decreasing the key value and BTL Analyze
deleting a node. 4
`

19 Differentiate Fibonacci heap and merge able heap. BTL Analyze

4
20 Classify on bounding on maximum degree. BTL Apply
3
PART-B
1 i).Define Binary Search Tree. BTL Remember
ii).List the features of binary search tree with an example. 1

2 i).Give an example for insertion in B Tree. BTL Understand

ii).Summarize the features of B Tree. 2

3 Express in detail about querying Binary search tree.. BTL Understand

2
4 Solve the insertion and deletion logic in BTL Apply
W,R,G,P,F,U,K,C,A,Z for B Tree 3

5 Demonstrate the basic operations with an example. BTL Remember

i) B tree. 1
ii) Binary search tree.

6 i).Point out the basic operations of Binary search tree BTL Analyze
ii).Compare and contrast B Tree and Binary search tree 4

7 Evaluate the features of Red Black Tree with an example. BTL Evaluate
5
8 i).Classify the insertion process of Red Black tree BTL Analyze
ii).Analyze on rotation of a node. 4

9 Formulate the basic operations of B Tree... BTL Create

6
10 Elaborate in detail about the following BTL Remember
i).Deletion operation of B Tree 1
ii).Give your example for the above

11 Explain Fibonacci Heap by constructing its structure. BTL 4 Analyze

12 List and explain the various operations of merge able heap BTL Remember
with an example. 1

13 Illustrate the following in detail BTL Apply

i).Fibonacci Heap structure 3
ii).Merge able Heap operations

14 Discuss the following in detail BTL Understand

i). Decreasing the key and deletion. 2
ii).Bonding on maximum degree.
`

UNIT V
PART-A
Q.No Questions BT Competence
Level
1 Distinguish strong connectivity and weak connectivity. BTL Understand
2
2 Define the term minimum cost spanning tree BTL Remember
1
3 Give an example for minimum cost spanning tree BTL Understand
2
4 Compare depth first and breadth first. BTL Analyze
4
5 What is biconnectivity? BTL Remember
1
6 Define directed graph. BTL Remember
1
7 State strong connectivity. BTL Remember
1
8 Evaluate the path finding problems. BTL 5 Evaluate

9 Formulate a transitive closure algorithm. BTL Create

6

10 Analyze the shortest path algorithm. BTL Analyze

4
11 Integrate the list of path problems. BTL Create
6
12 State an example for matrix multiplication BTL Remember
1
13 Summarize the path algorithm for matrix operation. BTL Understand
2
14 Quote the term single source problem. BTL 1 Remember

15 Point out the path finding algorithms BTL Analyze

4
16 Show the difference in directed and undirected graph. BTL Apply
3
17 Illustrate the dominators in directed graph. BTL Apply
3
18 Assess the difference between cyclic and acyclic graph BTL Evaluate
5
19 Differentiate directed and undirected graph BTL Understand
2
20 Demonstrate the term biconnectivity. BTL Apply
3
PART-B
1 i).List the features of spanning tree BTL Remember
ii). Identify the characteristics of minimum cost spanning tree. 1

2 Elaborate in detail the minimum cost spanning tree BTL Remember

1
`

3 i).Give the briefing of biconnectivity. BTL Understand

ii).Identify the algorithm for depth first search. 2

4 Express the steps for depth first search with an example, BTL 2 Understand

5 i). Analyze the steps for depth first search BTL Analyze
ii).What do you understand by biconnectivity 4

6 i).Define strong connectivity. BTL Remember

ii).Examine depth first search with an example 1

7 i).Demonstrate path finding algorithms BTL Apply

ii).Illustrate transitive closure algorithm 3

8 i).Evaluate the advantages of path finding algorithm. BTL Evaluate

ii).Summarize the concept of strong connectivity. 5

9 Design a shortest path algorithm with an example BTL Create

6
10 Classify the term transitive closure algorithm. BTL Analyze
4
11 Point out the following in detail BTL Analyze
i).Path finding algorithm 4
ii).Shortest path algorithm.
12 Describe in detail about the depth first search with own BTL Remember
example. 1
13 Discuss on single source problem and path problems in matrix BTL Understand
multiplication 2
14 Calculate the performance of dominators in directed acyclic BTL Apply
graph 3
`