ADVANCED DATA STRUCTURES & ALGORITHM ANALYSIS
Course Objectives:
The main objectives of the course is to
provide knowledge on advance data structures frequently used in Computer Science
Domain
Develop skills in algorithm design techniques popularly used
Understand the use of various data structures in the algorithm design
Course Outcomes: After the completion of the course students will be able to
CO1
Learn advanced data structures like AVL Trees, B-Trees, Heap Trees, and Graphs,
and understand their operations and applications.
CO2
Gain skills in designing algorithms using methods like Divide and Conquer and
Greedy approaches to solve problems.
CO3
Apply dynamic programming, backtracking, and branch-and-bound techniques to
solve optimization problems.
CO4
Understand NP-Hard and NP-Complete problems and explore methods for solving
graph and scheduling problems.
UNIT – I
Algorithm Analysis, Tree Heaps and Graphs Data Structures
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.
Heap Trees (Priority Queues) – Min and Max Heaps, Operations and Applications.
Graphs – Terminology, Representations, Basic Search and Traversals, Connected
Components and Bi-connected Components, Applications
UNIT – II
Divide and Conquer, Greedy Method
Divide and Conquer: The General Method, Quick Sort, Merge Sort, Strassen’s matrix
multiplication, Convex Hull.
Greedy Method: General Method, Job Sequencing with Deadlines, Knapsack
Problem, Minimum Cost Spanning Trees, Single Source Shortest Paths
UNIT – III
Dynamic Programming, and Optimization Problems
Dynamic Programming: General Method, All Pairs Shortest Paths, Single Source
Shortest Paths – General Weights (Bellman Ford Algorithm), Optimal Binary Search
Trees, 0/1 Knapsack, String Editing, Travelling Salesperson Problem.
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
Salesperson Problem.
UNIT – IV
NP Problems
NP Hard and NP Complete Problems: Basic Concepts, Cook’s Theorem
NP Hard Graph Problems: Clique Decision Problem (CDP), Chromatic Number
Decision Problem (CNDP), Travelling Salesperson Decision Problem (TSP)
NP Hard Scheduling Problems: Scheduling Identical Processors, Job Shop Scheduling
Textbooks:
1. Fundamentals of Data Structures in C++, Horowitz, Ellis; Sahni, Sartaj;
Mehta,Dinesh, 2ndEdition Universities Press
2. Computer Algorithms in C++, Ellis Horowitz, SartajSahni,
SanguthevarRajasekaran, 2nd Edition University Press
Reference Books:
1. Data Structures and program design in C, Robert Kruse, Pearson Education Asia
2. An introduction to Data Structures with applications, Trembley& Sorenson,
McGraw Hill
3. The Art of Computer Programming, Vol.1: Fundamental Algorithms, Donald E
Knuth, Addison-Wesley, 1997.
4. Data Structures using C & C++: Langsam, Augenstein&Tanenbaum, Pearson,
1995
5. Algorithms + Data Structures & Programs:, [Link], PHI
6. Fundamentals of Data Structures in C++: Horowitz Sahni& Mehta, Galgottia Pub.
7. Data structures in Java:, Thomas Standish, Pearson Education Asia
Online Learning Resources:
1. [Link]
2. [Link]
3. Abdul Bari,Introduction to Algorithms ([Link])