advance data struct and algorithm

20A05301T – Advanced Data Structures & Algorithms
Regulation – R20




Course Code Advanced Data Structures & Algorithms (Common L T P C
20A05301T to CSE, IT, CSE( DS), CSE (IoT), CSE (AI), CSE 3 0 0 3
(AI & ML) and AI & DS)
Pre-requisite Data Structures Semester III
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 algorithms, polynomial and non-polynomial problems.
Course Outcomes (CO):
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.
UNIT - I Introduction to Algorithms 9 Hrs
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, Analysing Recursive Programs.
UNIT - II Trees Part-I 8 Hrs
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 8 Hrs
Trees Part-II
Red-Black Trees, Splay Trees, Applications.

,Hash Tables: Introduction, Hash Structure, Hash functions, Linear Open Addressing, Chaining and
Applications.
UNIT - IV Divide and conquer, Greedy method 9 Hrs
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 9 Hrs
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

CONTENTS
1 Unit-I : Page NO
1.1 Introduction 1
1.2 Unit-I notes 1-16
1.3 Part A Questions 17
1.4 Part B Questions 18
2 Unit-II :
2.1 Introduction 19
2.2 Unit-II notes 19 - 41
2.3 Part A Questions 42
2.4 Part B Questions 44
3 Unit-III :
3.1 Introduction 45
3.2 Unit-III notes 45 - 61
3.3 Part A Questions 62
3.4 Part B Questions 64
4 Unit-IV :
4.1 Introduction 65
4.2 Unit-IV notes 65 - 98
4.3 Part A Questions 99

, 4.4 Part B Questions 100
5 Unit-V :
5.1 Introduction 101
5.2 Unit-V notes 101 - 141
5.3 Part A Questions 142
5.4 Part B Questions 145