23CS21T1 - ADVANCED DATA STRUCTURES & ALGORITHM ANALYSIS
(Common to CSE, CSE (DS), CSE (AI&ML), AI&DS, and IT)
Course
Professional Core Credits: 3
Category:
Course
Theory Lecture-Tutorial-Practical: 3-0-0
Type:
Data Structures, Algorithms, and Strong Sessional Evaluation: 30
Prerequisite: programming skills in at least one high-level Univ. Exam Evaluation: 70
language Total Marks: 100
• To provide knowledge on advance data structures frequently used in Computer
Science domain.
Objectives: • To develop skills in algorithm design techniques popularly used.
• To understand the use of various data structures in the algorithm design.
Upon successful completion of the course, the students will be able to:
Illustrate the working of the advanced tree data structures and their applications
CO1
(L2). Analyze algorithms with respect to space and time complexities (L4).
Understand the Graph data structure, traversals and apply them in various
CO2
contexts. (L2)
Course
Outcomes Use greedy methods and dynamic programming to solve optimization
CO3
problems.(L3)
Use backtracking and branch and bound for solving scheduling, resource
CO4
allocation, and pathfinding problems.(L3)
Understand the fundamental concepts of NP-Hard and NP-Complete problems
CO5
(L2) and will be able to analyze NP-Hard problems in graph theory. (L4)
UNIT-I
Introduction: Introduction to Algorithm Analysis, Space and Time Complexity
Analysis, Asymptotic Notations.
AVL Trees: Creation, Insertion, Deletion operations and Applications.
B Trees: Creation, Insertion, Deletion operations and Applications.
UNIT-II
Heap Trees (Priority Queues): Min and Max Heaps, Operations and Applications.
Graphs: Terminology, Representations, Basic Search and Traversals, Connected
Course Components and Bi connected Components, applications.
Content Divide and Conquer: The General Method, Quick Sort, Merge Sort, Strassen’s matrix
multiplication, Convex Hull.
UNIT-III
Greedy Method: General Method, Job Sequencing with deadlines, Knapsack Problem,
Minimum cost spanning trees, Single Source Shortest Paths - Dijkstra’s.
Dynamic Programming: General Method, All pairs shortest paths, Optimal Binary
Search Trees, 0/1Knapsack, String Editing, Travelling Salesperson problem.
UNIT-IV
Backtracking: General Method, 8-Queens Problem, Sum of Subsets problem, Graph
Coloring, 0/1 Knapsack Problem.
Branch and Bound: The General Method, 0/1 Knapsack Problem, Travelling Sales
person problem.
UNIT-V
NP Hard and NP Complete Problems: Basic Concepts, Cook’s theorem (Without
Proof).
NP Hard Graph Problems: Clique Decision Problem (CDP), Traveling Salesperson
Decision Problem (TSP)
NP Hard Scheduling Problems: Scheduling Identical Processors.
TEXT BOOKS:
1. Fundamentals of Data Structures in C++, Horowitz, Ellis; Sahni, Sartaj; Mehta,
Dinesh 2nd Edition Universities Press
2. Fundamentals of algorithms, Ellis Horowitz, Sartaj Sahni, Sanguthevar
Rajasekaran 2nd Edition University Press.
Text Books REFERENCE BOOKS:
&
1. Data Structures and program design in C, Robert Kruse, Pearson Education Asia
References
2. An introduction to Data Structures with Applications, Trembley & Sorenson,
Books
McGraw-Hill
3. The Art of Computer Programming, Vol.1: Fundamental Algorithms, Donald E
Knuth, Addison-Wesley, 1997.
4. Data Structures using C : Langsam, Augenstein & Tanenbaum, Pearson, 1995
5. Algorithms + Data Structures &Programs:,N.Wirth, PHI
6. Data structures in Java: Thomas Standish, Pearson Education Asia
1. https://www.tutorialspoint.com/advanced_data_structures/index.asp
E-Resources 2. http://peterindia.net/Algorithms.html
3. Abdul Bari, 1. Introduction to Algorithms (youtube.com)
